简介
btree：balance tree，平衡多叉树，类比avl：平衡二叉树，都是有平衡的属性 (多个子树高度一致)，只不过是二叉和多叉的区别。
使用场景
文件系统如extfs、jffs，sql，磁盘上的索引查找场景。多叉树的层级相比二叉树会更低，磁盘查找中，树的每一层访问相当于一次IO操作，多叉树会减少IO操作。
- 二叉树磁盘访问
如下实例7个索引，3层，3次IO操作。
- 多叉树
一个磁盘块可以保存多个索引，7个节点，2层，只有2次IO操作，多叉树有更少的IO操作。
btree中的概念
-
多叉树顺序：从左往右数字增长。
-
btree的节点
一个节点中可以有：指针、数据 (key、value)
1）指针：指向子节点。
2）数据中有key 值 和 保存的具体数据。
叶子节点：只有数据，没有孩子节点，即指针为空。
- 阶数
一个节点最多有多少个孩子节点。(指针个数)
- 指针和数据的个数：
1）数据比指针少1个
2）根节点最少1个数据
3）对于m阶btree，非根节点最少m/2 -1 个数据。
一个磁盘块一般保存一个节点。（磁盘索引特点，非btree的特点）
如何保证平衡
-
平衡的概念：访问每个叶子节点的层级要尽可能一致，防止抖动太多。
-
平衡的定义：(类比)
avl：左右子树的高度差1;
rbtree：黑高；
btree: 所有叶子节点在同一层。
- 执行平衡的动作：
avl：左右旋转。
btree：分裂。
分裂操作
分裂 + 进位(上浮)
从节点中心分裂，分裂出来的节点 插入到父节点 (进位)。 上浮到根节点后层级变高。
插入 和 删除的操作：
参见：B树和B+树的插入、删除图文详解 - nullzx - 博客园 (cnblogs.com)
B+ tree
非叶子节点的数据中只有key，而没有value，这样一个磁盘块中可以保存更多的指针和key，分叉可以更多。
参见：BTree和B+Tree详解_b+brtt的结构图_菜鸟笔记的博客-CSDN博客
参考资料
BTree和B+Tree详解_b+brtt的结构图_菜鸟笔记的博客-CSDN博客文章来源：https://www.toymoban.com/news/detail-705798.html
B树和B+树的插入、删除图文详解 - nullzx - 博客园 (cnblogs.com)文章来源地址https://www.toymoban.com/news/detail-705798.html
到了这里，关于btree学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
