Ada*_*ies 3 database indexing b-tree linked-list
任何人都可以解释为什么数据库倾向于使用b树索引而不是有序元素的链表.
我的想法是:在B + Tree(大多数数据库使用)上,非叶节点是指向其他节点的指针的集合.每个集合(节点)都是有序列表.叶节点是所有数据指针所在的位置,是数据指针簇的链表.
非叶节点仅用于查找目标数据指针所在的正确叶节点.因为叶节点就像一个链表,那么为什么不只是取消树元素而只是拥有链表.可以提供元数据,其给出每个叶节点集群的最小值和最大值,因此应用程序可以只读取元数据并找到数据指针所在的正确叶.
需要明确的是,用于搜索随机访问的有序列表的最有效算法是二进制搜索,其性能为O(log n),与b树相同.使用链表而不是树的好处是它们不需要平衡.
这种结构是否可行.
Ada*_*ies 14
经过一些研究和论文阅读后,我找到了答案.
为了处理大量数据,如数百万条记录,必须将索引组织成簇.群集是磁盘上的一组连续扇区,可以快速读入内存.这些通常大约4096字节.
这些集群中的每一个都可以包含一组索引,这些索引可以指向磁盘上的其他集群或数据.因此,如果我们有一个链表索引,索引的每个元素都将由一个集群中包含的索引集合组成(比如说100).
因此,当我们寻找特定记录时,我们如何知道它所在的群集.我们执行二进制搜索以找到有问题的集群[O(log n)].
但是,要进行二进制搜索,我们需要知道每个聚类中值的范围,因此我们需要元数据来说明每个聚类的最小值和最大值以及该聚类的位置.这很棒.除非每个集群可以包含100个索引,并且我们的元数据也保存在单个集群上(对于速度),那么我们的元数据只能指向100个集群.
如果我们想要超过100个集群会发生什么.我们必须有两个元数据索引,每个索引指向100个集群(10 000个记录).那还不够.让我们添加另一个元数据集群,现在我们可以访问1 000 000条记录.那么我们如何知道我们需要查询三个元数据集群中的哪一个才能找到我们的目标数据集群.我们可以搜索一个然后另一个,但这不会扩展.所以我添加了另一个元元数据集群来指示我应该查询三个元数据集群中的哪一个来查找目标数据集群.现在我有一棵树!
这就是数据库使用树木的原因.它不是索引大小的速度,也不是索引引用其他索引的需要.我上面描述的是B +树 - 子节点包含对其他子节点或叶节点的引用,叶节点包含对磁盘上数据的引用.
唷!
我想我在我的SQL索引教程的第1章中回答了这个问题：http : //use-the-index-luke.com/sql/anatomy
关于您的特定问题，总结最重要的部分：
-来自“叶子节点”
索引的主要目的是提供索引数据的有序表示。但是，无法顺序存储数据，因为插入语句将需要移动以下条目以为新条目腾出空间。但是移动大量数据非常耗时，因此insert语句将非常慢。问题的解决方案是建立独立于内存中物理顺序的逻辑顺序。
-来自“ The B-Tree”：
索引叶节点以任意顺序存储-根据索引顺序，磁盘上的位置与逻辑位置不对应。就像电话簿中混排的页面。如果您在其中搜索“史密斯”，但首先在“罗宾逊”将其打开，则史密斯绝不会再回来了。数据库需要第二种结构来快速找到改组页面之间的条目：平衡的搜索树-简而言之：B树。