数据结构与算法 —— B - Tree 和 B + Tree

一、M 阶 B - Tree（B Tree） 特点

1. 所有节点中的 key 数量 <= m - 1。
2. 根节点的 key 数量 >= 1。
3. 非根节点至少含有 m / 2 个 key 。
4. 所有节点中的 key 都按照从小到大排列。每个 key 的左子树中所有 key 都小于它，其右子树中所有的 key 都大于它。
5. 所有的叶子节点都位于同一层。
6. 所有节点都存有索引和数据，即：key - value。

二、M 阶 B + Tree 特点

1. 所有节点中的 key 数量 <= m - 1。
2. 根节点的 key 数量 >= 1。
3. 非根节点至少含有 m / 2 个 key 。
4. 所有节点中的 key 都按照从小到大排列。每个 key 的左子树中所有 key 都小于它，其右子树中所有的 key 都大于它。
5. 所有的叶子节点都位于同一层。
6. 节点分为内部节点和叶子节点。内部节点只保存 key，即：索引。
7. 叶子节点保存所有的 key 和 value 。
8. 每个叶子节点都含有与其紧邻的叶子节点的地址，故形成了链表。

三、B + Tree 优势

1. 每一个节点存储的 key 更多，使得查询的 IO 次数更少。因为每个节点都保存在一个页的存储空间内，其存储空间是有限的，如果 data 很大，直接导致每个节点中包含的 key 变少，tree 的深度加大，从而导致了查询时磁盘 IO 的次数增加，性能下降。
2. 因为所有的 key - value 都保存在子节点中，每次查询都要到大子节点，使得查询的性能稳定。
3. 所有叶子节点形成一个双向链表，方便查找。

图片原网址：https://www.cnblogs.com/vianzhang/p/7922426.html

（SAW：Game Over！）