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+树查找更稳定（并不慢）；
注意:
-
一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。（每一个节点都是一页，也就是说双向链表连接的是一个一个的数据页，数据页中包含的数据可能是一行记录，也可能是多行记录。）
-
B+树索引并不能找到一个具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读人到内存，再在内存中进行查找，最后得到要查找的数据。
-
也就是说真正的数据是被存储在磁盘上的。