数据结构与算法分析笔记——B树
B树
AVL树的特征是，通过在插入或删除时的微调，使得整个树中任意节点的左子树和右子树之间的高度差不超过1。这样的结果是，整棵树的高度不至于太高。那么，如果我们想要得到一棵更低的树？该如何呢？合理的设想是增加每个节点的子节点数，比如说，把每个节点的子节点树从2增加到3或5，树的高度就会降得更低。这就是B树的由来。把一棵M阶B树和二叉树进行比较，有以下不同：
二叉树中，每个节点最多有两个子树，而B树中，每个节点最多有M个子树。二叉树中，每个节点中都存储着一项数据，而B树中，真正在数据都存储在树叶节点上，中间节点只存储帮助找到相应树叶的索引关键值。对M阶B树来说，每个中间节点如果有k个子树，则会存储k-1个关键值。每个树叶节点中会包含L/2到L个数据项，每个节点中的数据项或关键值都和其父节点中的关键值存在某种关联关系，以便于搜索。二叉树中，树叶节点的深度可能会相差1到2，而B树中，每个树叶节点都在同一层阶上。比如说，如下就是一棵二叉树到B树的转换：
直观的就可以看到，B树比二叉树更加的矮胖。也就是说，在最坏的情况下，B树的查找是要比二叉树快的。但是，由于B树所有数据都存在树叶上，所以，二叉树有可能直接在根节点就找到要找的数据，而B树，则仍需要通过不断索引，找到要找的树叶。也就是，在查询上来说，B树比二叉树更加的均衡。在插入和删除来说，B树必然要比二叉树更加复杂一些。
B树的意义——减少磁盘访问次数
用插入和删除时的效率来换取查询时的平衡，B树这样做是否值得？我们知道，B树这种数据结构，在数据库、ES等许多数据存储中间件中都有使用。所以，我们可以猜测，B树是有意义的，且意义重大。假设现在有足够多的数据，使得它们无法全部放到计算机的内存中，那么，它们就必然要存储到磁盘上。这时候，要读取数据，就必然要去读取磁盘。当程序涉及到磁盘IO的时候，由于磁盘读取的时间是远大于内存指令执行时间的，计算机每秒大约可以进行次磁盘访问，却可以执行大约5亿条指令。所以，这个时候，程序的运行时间就不再取决于程序表面的复杂度，而在于程序读取磁盘的次数。B树就刚刚好符合这样的需求。内存中有一棵高度为n的B树，其树叶上，存储的都是数据在磁盘中位置，那么，通过若干的指令和一次磁盘访问，就可以找到数据。又假如由于数据更多了，那么，我们可以考虑把n和n-1层都放在磁盘中，这样，需要的磁盘访问次数就是2。
B树的实现
这里，我们只是讨论B树的某种可能的实现，以帮助我们更深入的理解B树这种数据结构的内存含义。
关键值如何取
关键值如何取，一种可能的方式是根据子节点的值的最大值或最小值来界定。比如某个节点包含了两个关键值，2和6，那么，它就应该有三个子节点，n1,n2和n3。且有n1上的数据一定小于2，n2上的数据一定大于等于2且小于6，n3上的数据一定大于等于6。那么，有同学可能会问，大于6的都在n3上吗？当然不是，比如该节点向右有一个兄弟节点，也包含两个关键值，10和14，并有三个子节点，n4，n5和n6。那么，n3上的数据就应该是大于6且小于10。大于10的数据将会放到n4,n5或n6上。以上这种关键值的取法，适用于要存放的数据项有一个可以转化为数字的关键属性。事实上，关键值的取法还可以更灵活些，比如说，要存放的数据项有一个可以转化为一个英语单词的关键属性。那么，我们可以设计出一棵如下的B树：
第一层用于划分单词的长度，某长度上的单词较少，可以和其它合并到一起。以下若干层用于确定单词第1到第n个字母。那么，要寻找apple这个单词对应的数据项，可能的索引线就会是：5-a-p-p-l-e-apple。根据要存放的数据项的特征，还可以设计出更复杂的B树出来，总之，我们的目的就是不害怕程序的相对复杂，就是要达到减少磁盘访问次数的目的。当然了，这样设计出来的B树，可能已经不是一个普通的B树了，它可能已经具备了B树的某些变体的特质。
最少数据项的意义
前面提到，一个M阶B树，要求所有中间节点的儿子树在M/2到M之间，所有树叶节点上的数据项在L/2到L之间。最大值的设定容易理解，最小值的设定是为什么呢？这是为了避免B树的退化。如果不设定最小值，在某些极端情况下，某个B树中的节点的子树可能会变成2，1甚至0，也就是说，该子节点退化成了一棵二叉树。所以，最小值要求你在这样极端情况下，要去重新规划节点及节点中的关键值，以保持B树不退化。
B+树
B+树相比B树来说，主要有以下不同：
B树中，中间节点的关键值总比子节点少1，而B+树中，关键值和子节点树相等。B+树中，树叶节点会构建成一个链表。也就是说，不通过其父节点，可以直接按序遍历所有的树叶节点。B+树相比B树而言，最大的一个优势在就在于，查范围内批量数据时，只需要确定第一条数据所在的树叶节点，就可以通过链表直接定位到下一个树叶节点。所以，数据库采用的不是基本的B树，而是B+树。