[ 数据库索引 ] B树和B+树
B+树
B树(多路平衡查找树,基本特性同Ｂ+树)
B 树中的每个节点由两部分组成：
- 数据
- 指向孩子节点的指针
每一个节点最多包含k个孩子，k被称为B树的阶，k的大小取决于磁盘页的大小(一个节点一次IO，一页)
一个m阶的B树具有如下几个特征：
- 1.根结点至少有两个子女。
- 2.每个中间节点都包含k-1个元素和k个孩子，其中
m/2 <= k <= m - 3.每一个叶子节点都包含k-1个元素，其中
m/2 <= k <= m（这里就有时候会导致节点的拆分和合并，其实就是为了保持平衡） - 4.所有的叶子结点都位于同一层（有点搞不懂这是为什么？）
- 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
删除时的左右旋：
B+与B树的区别
- Ｂ树会将数据存放在非叶子节点上，B+树都是存储在叶子节点上，所以一个磁盘页能够容纳更多的索引节点元素
- B+ 以链表将数据来凝结起来（主要是为了实现区间查找）
- B+树查询必须查找到叶子节点，B树只要匹配到即可不用管元素位置，因此B+树查找更稳定（并不慢）；