B+ 树
应用
在实际的数据库产品中，为了满足高效率的查找操作，我们需要实现某种索引来进行查找，索引又通常通过B+树或者B树去实现（一般不用红黑树）
为什么
考虑到索引文件一般也很大，不可能将它们全部存储在内存中，而是存储在磁盘上。又由于介质等原因的不同，磁盘的IO比主存的IO要慢很多。因此要想提高效率，必须要减少磁盘IO的次数。
为了达到这个目的，系统在发生缺页中断时都会直接读入一个block（page的整数倍）。假设B+树的高度为h，又因为通常设计成一个节点的大小对应于一个block，所以要查找特定的记录，最多只需要h次IO即可。
而红黑树的深度是远比B+树要高的，所以一般情况下都只会使用B+树
定义
一颗M阶B+树的定义
根节点只有一个，子树有[2, m]
除了根节点之外的非叶子节点，包含的子树为[[m/2],m]
所有非根节点的key数目为[[m/2], m]
叶子节点都在同一层，叶子节点才含有key的信息，其它只是索引
所有非叶子节点的key等于其子数中最大或者最小的key
操作
插入时判断其是否不满足定义，按需进行分解操作
删除时判断其是否不满足定义，按需进行合并操作v