B+ Tree

当我们在讨论链表、AVL Tree时，我们假设这些数据结构都可以完全的放在内存中。但当我们的数据量特别大时呢？这些数据就必须依赖于磁盘存储。那之前讨论的时间复杂度计算方式就存在问题，因为它假设所有的操作是均等的。但明显的内存读取和磁盘I/O是不一样的，因此我们需要尽量减少磁盘的访问。
假设我们有一批数据，总共1000万条数据，每一个key是32字节，每条记录256字节，我们假设这批数据超过了我们允许使用内存的数量。当我们需要访问某条数据时，如果使用普通的二分查找树，最坏的情况需要1000万次磁盘访问，AVL Tree会好一点但也需要大概25次访问。我们希望大大减少磁盘的访问，二叉树明显最多也是logN，显而易见的是假如我们有更多的分叉，我们就有更小的高度。例如，一个M-ary查找树允许有M个分叉，最终的高度可以表示为log_MN,为了保证M-ary查找树最坏的情况，我们也需要保证他是平衡的。
其中一种实现方式就是B+ Tree树了，一个M-ary的B+ Tree树的特征如下：

1. 数据存储在叶子节点
2. 非叶子节点有至多M - 1个keys方便查找，每一个key是下一个子树的最小值。
3. 根节点没有孩子或者有2-M个。
4. 所有的非叶子节点有M / 2(向上取整）到M个孩子节点。
5. 所有的叶子节点有相等深度，且有L/2(向上取整)到L个数据项。

例如一个5-ary的B+树，所有的非叶子节点有3到5个孩子。我们假设L也为5的话，叶子节点有3到5个数据项。真实情况中，我们通常会让一个节点等于一个磁盘块的大小。例如，一个磁盘块是8192个字节，我们上面的数据集中每一个key是32字节，M-ary树会有M-1个key因此大小可以表示为32M - 32，考虑到还有M个分叉，算4个字节总共4M,最终一个节点的大小可以表示为36M - 32。因此我们可以算出M的大小为228，由于每一个数据记录是256字节，那么每一个块可以放32个数据项，那么每一个叶子节点就有16到32个数据项，非叶子节点就至少有114个孩子，1000万记录的话最多有625000个叶子，我们通常会将根节点或者直接与根节点相连的节点放在内存中，这样能够极大的减少磁盘访问。