B树
1.定义
首先，我们先明白这个逼树是要用来干嘛的？那绝对不只是用来面试的时候装逼的呀 (｀・ω・´)，那到底是干嘛的，跟之前的AVL有什么区别啊？
我们先明白一下什么是磁盘io，因为有时候数据结构太大，不能整个加载到内存，这个时候只能分次访问磁盘上的数据，比如之前的AVL如果很大，那么我们只能依次访问每个存储在磁盘上的树结点。
这个时候问题就来了，我们之前的树结构都是基于一样的操作速度，现在访问树节点的是磁盘操作，进行比较的是处理器的操作，所以我们要做出调整，降低AVL的高度来降低访问节点的次数，而比较的操作相对来说速度快很多，这个方面可以多点没关系。
明白了这个后，来看看阶为M的B树有什么特点：
a.数据项存储在树叶上
b.非叶结点存储直到M-1个键，用来划分子树的大小（类似于二叉树，但是二叉树只有一个值）
c.树的根是树叶，不然其儿子数在2~M之间
d.除了根，所有非树叶结点的儿子数在 M/2 ~M之间
e.所有的树叶在相同深度上并有 L/2 ~ L个数据项
2.例子
上面的定义有点模糊，来举个栗子好了~
这里是一个5阶B树的栗子，我们来依次分析上面的特点好了
a.树叶上可以看到[2, 4, 6]， [8, 10, 12, 14, 16]…这些都是数据项，其实就是我们要查找的值
b.可以看到第二层键的数目依次是4,3,3,2，范围在M-1内
c.略
d.略
e.这里的L是5，所以这个特点也满足了，至于L是如何决定，下面说明
设我们想要访问火星上公民的驾驶记录，有1000w项，每个键是32个字节(名字)，每个记录是256个字节（有没有醉驾之类的信息）。现在，假设每个结点是一个区块，可以容纳8192字节，那么在一颗M阶B树里，有M-1个键，总数为32M-32字节，再加上M个分支，每个分支是另外一些磁盘区块，可以假设为4个字节。那么一个非叶结点的内存一共是36M-32个字节。
如何决定M和L，36M-32 <= 8192，得到m = 228，另外每个数据是256字节，因此可以把32个记录转入一个区块，于是我们选择L=32，
那么这样就决定了M和L的大小了。由于有1000w个记录，那么最多有625000个叶结点(1000w/16)，由Logm/2(N)可以得到树叶最坏情况下会在第4层。
3.操作
a.插入
需要考虑插入的叶节点的大小超过L了没有，比如下面两种情况
插入57，插入57后再插入55，会变成下面的样子
又比如插入40后超过L了，要如何变化
b.删除
删除相对来说，需要考虑要不要合并
上面删除99的时候，设计到了相邻叶节点以及相邻父节点的合并
参考：《数据结构与算法分析》