首页 > 其他 > 详细

B树和B+树

时间:2020-04-30 09:07:56      阅读:51      评论:0      收藏:0      [点我收藏+]

B树:

1. B树中每个节点最多有m个孩子,称为m阶B树。

2. 根节点至少有两个孩子。

3. 所有的叶子节点都位于同一层。

B树的目的是让每一个索引块尽可能存储更多的信息。与平衡二叉查找树不同,B树主要是为优化大块数据的读写操作而设计的。普遍应用在数据库和文件系统。

B+树是B树的一种变体:

1. B+树中的节点指针数目与关键码的数目相同

2. 跟记录有关的数据均位于叶子节点中,非叶节点仅具有索引作用

3. 树的所有叶节点构成一个有序链表,可以根据关键码的排序次序遍历全部记录。

 

数据库为什么选择B+树索引?而map使用红黑树索引?

因为外存(磁盘)和内存差异。数据库的查询是在磁盘中,读取到数据之后存储在索引结构中。磁盘每次读取的最小单位是一簇。

而map位于内存中,可以按位读取。

红黑树是二叉树,在数据库中使用红黑树会使得索引过于庞大。而内存中需要进行频繁的插入操作,如果使用B+树则修改量会很大。

 

B树和B+树

原文:https://www.cnblogs.com/conanpeng/p/12806249.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!