加入收藏 | 设为首页 | 会员中心 | 我要投稿 惠州站长网 (https://www.0752zz.com.cn/)- 办公协同、云通信、物联设备、操作系统、高性能计算!
当前位置: 首页 > 运营 > 正文

数据存储检索之B+树

发布时间:2021-03-12 11:07:16 所属栏目:运营 来源:互联网
导读:为了加速数据库数据的访问,大多传统的关系型数据库都会使用特殊的数据结构来帮助查找数据,这种数据结构叫作索引( Index)。对于传统的关系型数据库,考虑到经常需要范围查找某一批数据,因此其索引一般不使用 Hash算法,而使用树( Tree)结构。然而,树结构

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

二叉查找树与平衡二叉树

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

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

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

B+树

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

(编辑:惠州站长网)

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

    推荐文章
      热点阅读