数据存储检索之B+树

为了加速数据库数据的访问，大多传统的关系型数据库都会使用特殊的数据结构来帮助查找数据，这种数据结构叫作索引( Index)。对于传统的关系型数据库，考虑到经常需要范围查找某一批数据，因此其索引一般不使用 Hash算法，而使用树( Tree)结构。然而，树结构的种类很多，却不一定都适合用于做数据库索引。

二叉查找树与平衡二叉树

最常见的树结构是二叉查找树( Binary Search Tree)，它就是一棵二叉有序树：保证左子树上所有节点的值都小于根节点的值，而右子树上所有节点的值都大于根节点的值。其优点在于实现简单，并且树在平衡的状态下查找效率能达到 O(log n);缺点是在极端非平衡情况下查找效率会退化到 O(n)，因此很难保证索引的效率。
 

针对上述二叉查找树的缺点，人们很自然就想到是否能用平衡二叉树( Balanced Binary Tree)来解决这个问题。但是平衡二叉树依然有个比较大的问题：它的树高为 log n——对于索引树来说，树的高度越高，意味着查找所要花费的访问次数越多，查询效率越低。

况且，主存从磁盘读数据一般以页为单位，因此每次访问磁盘都会读取多个扇区的数据(比如 4KB大小的数据)，远大于单个二叉树节点的值(字节级别)，这也是造成二叉树相对索引树效率低下的原因。正因如此，人们就想到了通过增加每个树节点的度来提高访问效率，而 B+树(B+-tree)便受到了更多的关注。

B+树

在传统的关系型数据库里， B+树( B+-tree)及其衍生树是被用得比较多的索引树。

（编辑：惠州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!