B树(B-树)、B+树、R树简介

B树(B-树)

磁盘读取数据是以盘块」 (block)为基本单位的。「位于同一盘块中的所有数据都能被一次性全部读取出来。
而磁盘IO代价主要花费在查找时间Ts上。
因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。
或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间 Ts」。

所以，在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(block)
中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构，
就是下面所要重点阐述的B-tree结构，以及相关的变种结构：「B+-tree结构和B*-tree结构。」

B树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。与红黑树很相似，但在降低磁盘I/0操作方面要更好一些。
许多数据库系统都一般使用B树或者B树的各种变形结构，如下文即将要介绍的B+树，B*树来存储信息。

B+树

是应文件系统所需而产生的一种B-tree的变形树.

所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(
而B 树的叶子节点并没有包括全部需要查找的信息)
「所有的非终端结点可以看成是索引部分」，结点中仅含有其子树根结点中最大（或最小）关键字。(而B
树的非终节点也包含需要查找的有效信息)

为什么说 B+-tree 比 B 树更适合实际应用中操作系统的文件索引和数据库索引？

B+-tree的磁盘读写代价更低

「B+-tree」 的内部结点并没有指向关键字具体信息的指针。
 因此其内部结点相对 B 树更小。
 如果把所有同一内部结点的关键字存放在同一盘块中，
 那么盘块所能容纳的关键字数量也越多。
 一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

B+-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。
所以任何关键字的查找必须走一条从根结点到叶子结点的路。
所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B+树便于范围查询（最重要的原因，范围查找是数据库的常态。且支持扫库。）

B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，
正是为了解决这个问题，B+树应用而生。
B+树只需要去遍历叶子节点就可以实现整棵树的遍历。
而且在数据库中基于范围的查询是非常频繁的，
而B树不支持这样的操作或者说效率太低。

B*-tree

B-tree是 B+-tree 的变体，
在 B+ 树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，
B树中非根和非叶子结点再增加指向兄弟的指针；
B 树定义了非叶子结点关键字个数至少为(2/3)M，
即块的最低使用率为2/3（代替B+树的1/2）。

B*-tree

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，
最后在父结点中增加新结点的指针； B+树的分裂只影响原结点和父结点，
而不会影响兄弟结点，所以它不需要指向兄弟的指针。

*B树的分裂**：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，
再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；
如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

*所以，B树分配新结点的概率比B+树要低，空间使用率更高。**