B 树

• 每个节点最多有 m - 1 个关键字（能够存有的键值对）。
• 根节点起码能够只有 1 个关键字。
• 非根节点至多有 m / 2 个关键字。
• 每个节点中的关键字都依照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都雷同。
• 每个节点都存有索引和数据，也就是对应的 key 和 value。

• 所以，根节点的关键字数量范畴：1 <= k <= m-1，非根节点的关键字数量范畴：m/2 <= k <= m-1

  插入

  直接插入到叶节点的对应地位，如果数量超过 m 则决裂，将两头 k 回升到父结点中

删除

间接删除，如果删除后数量少于 m /2（m/2-1），则从兄弟节点中借 k（兄弟节点 k 回升到父节点，父节点中一个 k 降落到以后节点中），如果兄弟节点中没有能借的 k（数量不多于 m /2），则与兄弟节点合并（此时会从父节点中借一个 k）。

B+ 树

B+ 树其实和 B 树是十分类似的，咱们首先看看相同点。
相同点：

• 根节点至多一个元素
• 非根节点元素范畴：m/2 <= k <= m-1

不同点：

• B+ 树有两种类型的节点：外部结点（也称索引结点）和叶子结点。外部节点就是非叶子节点，外部节点不存储数据，只存储索引，数据都存储在叶子节点。
• 外部结点中的 key 都依照从小到大的顺序排列，对于外部结点中的一个 key，左树中的所有 key 都小于它，右子树中的 key 都大于等于它。叶子结点中的记录也依照 key 的大小排列。
• 每个叶子结点都存有相邻叶子结点的指针，叶子结点自身依关键字的大小自小而大程序链接。
• 父节点存有右孩子的第一个元素的索引。

B 树和 B + 树

• 繁多节点存储的元素更多，使得查问的 IO 次数更少，所以也就使得它更适宜做为数据库 MySQL 的底层数据结构了。
• 所有的查问都要查找到叶子节点，查问性能是稳固的，而 B 树，每个节点都能够查找到数据，所以不稳固。
• 所有的叶子节点造成了一个有序链表，更加便于查找。