二叉排序树是 由树到索引(3)

再来做一个思考，对于n个关键字的m阶树，最坏需要需要几次查找？

1.因为根至少有两个孩子，因此第2层至少有两个结点。

2.除去跟结点和叶子外，每个分支的结点至少都有m/2个孩子；

3.第三层结点的个数2*m/2个节点；

4.第四层结点的个数2*(m/2)^2个结点；

5.第K+1层结点的个数2*(m/2)^k-1个结点，这里K+1层就是叶子结点；

6.B树有n个关键字，当你找到叶子节点，就等于查找不成功的结点为n+1,因此n+1>=2*(m/2)^k-1,即k<=log(m/2)((n+1)/2)+1；

7.结论根结点到关键字结点涉及的结点个数不操过k<=log(m/2)((n+1)/2)+1；

总结如下，一颗n个关键字结点的m阶树最大高度为k<=log(m/2)((n+1)/2)+1，B树的每个非根的分支节点m个孩子，其中 m/2 <= m<= m,随着m的增加，B树的高度下降，查找性能提升；

B+树：

接下来我们继续探讨一个问题，看下图，当我们对B树进行中序遍历的时候，假设每一个结点都在硬盘不同的页面上，这个时候必然会经过页2---页1--页3--页4--页1---页4---页1---页5，这样会导致每次那一个元素都要对结点的元素进行遍历，我们有没有什么办法让元素只被访问一次，带着这个问题我们来看下B+树。

接下来我们还是老套路看图说话，下图是一颗B+树，其有如下特点：出现在分支结点中的元素会被当作分支结点位置的中序后继结点再次列出，另外每个叶子结点都会保存一个执行后一个叶子结点的指针。

一颗m阶树的B+树和m阶的B树差异如下：

1.n颗子树的结点包含n个关键字；

2.所有的叶子结点包含全部关键字的信息，以及指向这些关键字记录的指针，叶子结点本身按照从小到大的顺序进行排列；

3.所有分支结点都可以看成索引，结点中含有子树的最大(或最小)关键字。

如果上面的B+树看的还不是很直观，那么我们再来看一颗更直观一点的；这里我们就不谈什么页分裂问题，这个问题待索引的时候再来探讨，我们来说下B+树和B树在查找方面的比较，首先2者与二叉树比较，提升了磁盘I/O效率，但是B树没有解决遍历元素时效率低的问题，如同上面提出的那个问题，这里我们可以通过B+树来解决，B+树只需要通过叶子节点遍历就可以实现对整棵树的遍历。B+更大的优势在于范围查找，这一点是B树无法比较的，进行范围查找是只需要在叶子结点上遍历即可。B+树的插入和删除都与B树类似，但是插入和删除都是在叶子结点上进行。

上面介绍树的几种不同的数据结构，主要是为了引出B+树，明白这种结构的好处才能为我们后面索引打下基础，另外这里没有介绍红黑树，这个等HashMap源码解读的时候再来看，Java代码实现主要提供平衡二叉树的实现，B树的实现还是给大家提供一个参考https://github.com/int32bit/algorithms/blob/master/B-Tree/src/BTree.java；

二、Java代码实现

三、索引

已经探讨B+树的好处，接下来我们来看一下B+插入和删除操作；

插入操作：

B+树插入必须保证插入后的叶子结点记录依然排序，另外还需要考虑插入到B+树的三种情况，接下来我们来谈一下这3种情况：

1.当Leaf Page和Index Page都未满的时候，直接将记录插入到叶子节点即可（Leaf Page和Index Page分别指的是叶子结点和父亲结点）;

当插入28这个值的时候，Leaf Page和Index Page都未满，直接插入到叶子节点

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-68999-3.html