数据存储检索之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)及其衍生树是被用得比较多的索引树。 (编辑:惠州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |