数据库-3.4 优化你的索引-运用B+树

B+树是B树的变体，其定义基本上与B树相同，除了：
1，非叶子节点的子树指针与关键字个数相同；
2，非叶子节点的子树指针P[i]，指向关键字值[K[i],K[i+1])的子树；
如下图，我们把K[i]设为10，那么K[i+1]就是20，那么可以看到10对应的子树里面的值均小于20，同时均大于或等于10。
3，非叶子节点仅用来索引，数据都保存在叶子节点中；
也就是说，当咱们要搜索10相关的数据的时候，并不能停止搜索，必须搜索到叶子节点当中，因为叶子节点才存储了我们需要用到的数据，那是什么数据呢？有的可能是指向数据文件的指针，有的也可能是主键的值，或者有的就干脆存储在这个节点上面了。总之，它是会存储到叶子节点当中的，这也就表明了，B+树所有索引都是从根部开始，检索到叶子节点才能结束，同时非叶子节点仅用来存储索引，非叶子节点不存储数据，又能存储更多的关键字，那也就使得我们的B+树相对于B树来说更矮。咱们的B树，它的搜索可以在任意一个非叶子节点就终结掉了，也就是说它可能把数据文件存储在非叶子节点上。
4，所有叶子节点均有一个链指针指向下一个叶子结点，并按大小顺序链接。
那把这些叶子节点链接起来有什么用呢？如下图，大家可以看到，B+树的叶子节点都是按照大小顺序来做排列的，链接起来，能够方便我们直接在叶子节点做范围统计。比如我们要搜索大于或者等于10的数据，我们定位到10所在的叶子节点之后，它就会直接从这里往后统计，而不是再回到根节点去做搜索了，也就是说，它支持范围统计，比如大于或等于10这样去做一个范围统计，即一旦定位到某个叶子节点，便可以从该叶子节点开始，横向地去跨子树去做统计。

经过上面的分析，咱们得出一个结论：B+树更适合用来做存储索引。
B+树相比于B树，还有其他树来说，在文件系统以及数据库系统中，更有优势，原因如下：
1，B+树的磁盘读写代价更低。
B+树的内部结构并没有指向关键字具体信息的指针，也就是不存放数据，只存放索引信息，因此，其内部节点相对于B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，这个盘块所能容纳的关键字数量也越多，一次性读入内存中的需要查找的关键字也就越多，相对来说，IO读写次数也就降低了。
2，B+树的查询效率更加稳定。
由于内部节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引，所以任何关键字的查找必须走一条从根节点到叶子节点的路，所有关键字查询的长度相同，导致每一个数据的查询效率也几乎是相同的，稳定的O(logn)。
3，B+树更有利于对数据库的扫描。
B树在提高了磁盘的IO性能的同时，并没有解决元素遍历效率低下的问题。而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描。所以对于数据库中频繁使用的范围查询，有着更高的性能，这也是为什么选择B+树做主流数据结构的原因。