B树和B+树
B树
类似于这种
一个m阶的B树有以下特征:
- 根节点至少有两个孩子。
- 每个中间节点都包含k-1个元素和k个孩子,其中m/2<=k<=m
- 每一个叶子节点都包含k-1个元素,其中m/2<=k<=m
- 所有的叶子节点都位于同一层
- 每个节点元素从小到大排列,节点当中的元素正好是孩子包含的元素值域分划(比如2 6 节点的孩子3 5节点正好在2和6之间,2 6又在1 8 之间)
特点:
-
高度相对于二叉平衡树低,查询次数虽然和二叉平衡树差不多,但是减少了最耗时间的IO操作
-
在插入删除元素时,可以通过拆分左旋等操作让树进行自平衡
应用:
文件系统,部分数据库索引(比如MongoDB)等。
B+树
类似于这种
一个m阶的B+树有以下特征:
- 有k个子树的中间节点包含有k个元素(B树是k-1个元素)每个元素不保存数据,只用来当索引,所有的数据都保存在叶子节点。
- 所有的叶子节点包含了全部元素,每一个叶子节点都有指向下一个叶子节点的指针,形成了一个有序链表。
- 每一个父节点的元素都出现在子元素中,是子节点最大(或最小)元素。
关于卫星数据:
索引元素所指向的数据记录,比如索引指向数据库中某一行。
B+树和B树的区别:
- 在B树中,无论中间节点还是叶子节点都有卫星数据,而在B+树中只有叶子节点有,其余节点只是索引,没有数据关联。且B+树由于没有卫星数据,同样大小的磁盘页就可以存放更多数据。
- 如果B+树和B树数据量相同,B+树更加矮胖,查询IO操作更少。
- B+树查询必须查找到最后的叶子节点,而B树找到匹配元素即可(无论在中间节点还是叶子节点),所以B树的查找性能可能不稳定,B+树则很稳定。
- 进行范围查询时,B树要查询两个节点之间的所有元素,要做很多IO操作。而B+树只要找到边界元素延后根据链表遍历到另一个边界元素即可。
参考资料:
https://mp.weixin.qq.com/s/rDCEFzoKHIjyHfI_bsz5Rw
https://mp.weixin.qq.com/s/jRZMMONW3QP43dsDKIV9VQ