B 树（B-Tree）是为磁盘等辅助存取设备、文件系统和数据库 设计的一种平衡查找树，在降低磁盘 I/O 操作次数方面表现优异。
时间复杂度O(log n) 执行查找、顺序读取、插入和删除操作。
节点分为内部节点（Internal Node）和叶节点（Leaf Node）。内部节点可以包含 >= 2 个子节点，在设计时 可预先设定可包含子节点的数量范围。如 2-3 tree
度 阶 深度 高度 ？
最小子节点数为度，最大子节点数为阶。深度（Depth）描述树中层的数量。
B 树通过要求所有叶节点保持在相同深度来保持树的平衡。深度通常会随着键值的不断添加而缓慢地增长。
当向节点插入或删除数据时，意味着子节点的数量发生变化。为了维持在预先设定的数量范围，内部节点可能会被合并（Join）或拆分（Split）。因为子节点的数量有一定的范围，所以 B 树不需要频繁变化以保持平衡。
键值（Key）扮演着分割子节点的角色。
如，假设某内部节点包含 3 个子节点，则实际上必须有 2 个键值：a1 和 a2。
a1 的左子树上的所有的值都要小于 a1， a1 a2 之间的子树中的值都大于 a1 小于 a2，a2 的右子树上的所有的值都大于 a2。
（见下图）
B 树 操作
-
查询
从根节点开始查询，通过递归进行自顶向下的遍历。在每一层上，将查询键值与内部节点中的键值比较，以确定向哪个子树中进行遍历。
查询9在x中的位置，c1234为子树。
-
插入
当要插入一个新的值时，首先在树中找到该值应当被插入的叶节点的位置：
如果叶节点包含键值的数量在设定的范围上界和下界内，则直接插入新键值，并保持键值在节点中顺序。
否则，节点已满，将节点分割为 2 个节点：
选择中间值（Median）作为分割点；
小于中间值的键值放入新的左节点中，大于中间值的键值放入新的右节点中；
将中间值插入到父节点中。此时可能导致父节点满，采用同样方式分割。如果父节点不存在，比如是根节点，则创建一个新的父节点，也就导致树的高度增长。
+9表示插入9，-9表示删除9
B树的变种 B+ tree
在内部节点中存储的键值同样也会出现在叶节点中，但内部节点中不存储 pointers to data records。
在叶节点中的不仅存储键值，还存储 pointers to data records。
此外，叶节点还增加了一个指向下一个顺序关联叶节点的指针，以改进顺序读取的速度。
B+ 树的优势在于：
- 由于内部节点不存储键值关联的附属数据，所以内部节点节省的空间可以存放更多的键值。也就意味着从磁盘存取一页时可获得更多的键值信息。
- 叶节点形成了一个链，所以对树的全扫描就是对所有叶节点的线性遍历。
网友评论