B树
B树简介
B树（B-tree）是一颗多路平衡查找树。
B树特性
==m为B树的阶数==
所有节点关键字是按递增次序排列，并遵循左小右大原则。
1 < 非叶节点的子节点数 <= M（M>=2，空树除外）。
除根结点和叶子结点外，其它每个结点有$ceil(m / 2)$个孩子。
- 所有叶子结点都出现在同一层，叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为 null。
- 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
- Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
- Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
- 关键字的个数n必须满足：$ ceil(m / 2)-1<= n <= m-1$
B树查询流程
如上图我要从上图中找到E字母，查找流程如下
- 获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）。
- 拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点。
- 拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）。
B树插入流程
定义一个5阶树（平衡5路查找树），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来。
遵循规则：
- 节点拆分规则：当前是要组成一个 5 路查找树，那么此时 m = 5 ，关键字数必须 <= 5 - 1（这里关键字数 > 4 就要进行节点拆分）。
- 排序规则：满足节点本身比左边节点大，比右边节点小的排序规则。
先插入 3、8、31、11
再插入23、29
再插入50、28
B树删除流程
节点合并规则：当前是要组成一个 5 路查找树，那么此时 m = 5 ,关键字数必须大于等于 $ceil(m/2)-1$ （这里关键字数 < 2 就要进行节点合并）。
满足节点本身比左边节点大，比右边节点小的排序规则。
关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放。
B树特点
B树相对于平衡二叉树的不同：每个节点包含的关键字增多了，特别是在 B 树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为 4K ，每次 IO 进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围。把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。