数据结构之B树

B数是为了解决磁盘读取速度和CPU运算速度不匹配的问题而产生的，因为类似的动态查找树的查找速度都是和树的深度有关系的，如果数据太庞大，不可能一次性读入内存，那么必然回放入外存，于是CPU发送每一次查找指令都必须去磁盘查找，而这个过程就是相当漫长的。B数具体分为B+树，B-树，B*树。这里记录一下B+树的学习过程。一颗完全二叉树的高度大约是log2(N)，然后一颗完全的M叉树的深度是logM(N)，自然深度降了很多。为了避免像不平衡的二叉查找树那样退化到甚至变成一个链表，于是B+树有以下规定：

1. 数据项存储在树叶上。
2. 非叶节点存储M-1个关键字用来知识搜索的方向；关键字i代表下一棵子数中最小的关键字。
3. 树的根或者一片树叶，其儿子树必须在2和M之间。
4. 除根外，所有非树叶节点的儿子数在M/2（向上取整）和M之间。
5. 所有树叶都在相同的深度上并且有L/2和L之间和数据项。

这里L和M的大小确定？脑补一下，不能确定就去翻书109页。L的确定是根据磁盘的区块大小大小来确定的，比如一个区块有2000个字节，然后一个记录有10个字节，那么这个L就等于200,意思是每一个树叶节点可以保存200个记录。M大小的确定，还是比如一个区块有2000个字节，但是为了确定搜索方向必须有一些关键字，如果关键字的大小是20字节，在M阶B数中有M-1个关键字，然后还需要M个分支来指向下一个区块，每个分支占用4个字节，于是所需要的大小为20*（M-1）+4M。

B数的插入

这里涉及到分裂，比如当想插入一个数时，插入到一个叶子节点，然后该叶子节点的儿子数已经达到了M这个最大值，于是不能插入，这个时候就必须进行分裂，需要将这个叶子结点分裂成2个树叶，然后就能存下了，但是分裂成了两个树叶必然会导致，父节点多出一个儿子，当父节点儿子数已经是M的时候，这个时候酒还需要分裂父节点的父节点，直到达到根节点，这个时候就需要建立一个新的根作为分好的两个儿子的父亲，这也是唯一一个增加B数高度的方式。当然还可以将当前儿子树移到相邻节点领养。具体见《算法分析与设计》111页。

B数的删除

B数的删除择涉及到儿子的合并，因为父节点儿子有最少数量限制，父节点儿子数小于m/2时就需要和相临节点合并，或者从相邻节点领养一个儿子来维持自己。