B 树
B 树即 B-Tree，所以也叫 B- 树，也是一种自平衡搜索树，但他是多路查找树，也即多叉树。因为像 AVL 树，红黑树这样的自平衡二叉查找树在使用的时候往往认为数据都是存在内存里的，而 B 树的使用场景中往往数据很多，需要存在磁盘中，而对于查找这样的操作，每访问一次树节点就需要读一次磁盘，所以降低树的高度变得很关键，使用多叉树的数据结构也就很自然了。
B 树的性质：
- 所有叶子节点在同一层
- B 树有个很重要的属性叫做 minimal degree，用 t 表示，和磁盘的 block size 有关
- 根节点最少有 1 个 key，其他节点最少有 t-1 个 key
- 所有节点最多有 2t-1 个 key
- 一个节点的儿子数量等于该节点所含 key 的数量加 1，最多有 2t 个儿子，2t 也称为该 B 树的阶。也就是说每个节点中是一个指向儿子节点的指针，一个 key，这样间隔着排列，最后是指向儿子节点的指针。
- 节点中的 key 升序存储，k1 和 k2 之间的那个儿子节点所含的 key 一定在 k1 和 k2 范围内
- 查找，插入，删除的时间复杂度均为 O(logn)
B 树的插入，从根节点开始，一直寻找到叶子节点，直到找到一个合适的位置，插入 key。但是因为每个节点最多容纳 2t-1 个 key，所以当寻找的过程中遇到某个节点已经有 2t-1 个 key 时，会进行 split 操作，将已经存满 key 的节点一分为二，中间节点放到父节点中（注意父节点必不可能存满 key，因为是从父节点遍历下来的，如果父节点存满了，那在此之前父节点应该先被 split，这种策略称为 proactive insertion，主动插入；相对地，reactive insertion，被动插入是说只有当新的 key 真的要插入存满的节点时才 split，而不仅仅是遍历经过，这种策略有可能导致一路往上 split，浪费时间，但是主动插入也可能会导致过早的不必要的 split）
如果根节点存满了，就将根节点一分为二，将中间的 key 放入新的根节点，左右两边作为儿子节点挂到新的根节点下，这也是唯一增加树高的方式。
B 树的删除和 BST 类似，如果删除的是叶节点中的 key，直接删除（有可能需要修复）；如果删除的是树枝节点中的 key，将该 key 的后继提升上来，删除后继，由于后继一定存在于叶子节点中，所以也就化归成了删除叶节点中 key 的情况。
如果叶节点由于被删除了一个 key 而所含的 key 的个数不足 t-1 个了，则需要进行修复，修复过程从该叶节点开始。
- 如果待修复节点有兄弟节点所含的 key 个数多于 t-1，则从兄弟节点移一个 key 到父节点，再从父节点移一个 key 到待修复节点，修复结束。（注意如果不是叶子节点这一层的话，移动 key 的同时还要移动指向儿子节点的指针）
- 如果待修复节点的兄弟所含的 key 个数都是 t-1，不能从他们那里借，那只能进行合并，父节点中夹在待修复节点和兄弟节点之间的 key，以及待修复节点，兄弟节点的 key 合并成一个新的节点（新节点所含 key 的个数一定小于等于 2t-1）。然后将父节点标记为待修复节点。
循环直到待修复节点所含 key 的个数不少于 t-1 为止。如果根节点只剩一个 key，又由于上述合并操作需要从父节点拿一个 key，这可能会导致根节点不含任何 key 了，此时便删除根节点。
可见不管是插入还是删除，树高的变化总是从根节点开始的，这和 BST 不同，它的树高的变化是从叶节点开始的。
references:
B+ 树
- B+ 树和 B 树最大的区别就是树枝节点不保存 key，只用作索引，且每个叶子节点都有指向相邻叶子节点的指针。
- reference
B* 树
- B* 树在 B+ 树的基础上多了几条性质：
- 叶子节点最少要有 4t/3 个 key（即最少占 2/3），而不是原来的 t-1 个（最少占 1/2），好处是节点的空间使用率会变高
- 不仅叶子节点一层有指向兄弟节点的指针，所有树枝节点也加上了指向兄弟节点的指针，且存满时不会分裂，而是向兄弟节点转移 key，如果兄弟节点也满了，就各拿出 1/3 创建一个新的节点。猜想删除时如果余量不足了会从兄弟节点拿，兄弟节点 key 也不够了的话就删除一个兄弟节点把他所含的 key 均分给其他兄弟。
- reference