B-Tree/B+Tree概述
B-Tree的数据结构
为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]：
key为记录的键值，对于不同数据记录，key是互不相同的；
data为数据记录除key外的数据。
那么B-Tree是满足下列条件的数据结构：（其中，h为B-Tree的高度，d为B-Tree的度，且d>1，h>0）
每个非叶子节点由n-1个key和n个指针组成（其中d<=n<=2d），且这些key是有序的；
每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null ；
所有叶节点具有相同的深度，等于树高h；
key和指针互相间隔，节点两端是指针；
一个节点中的key从左到右非递减排列。
所有节点组成树结构。
每个指针要么为null，要么指向另外一个节点。
如果某个指针在节点node最左边且不为null，则其指向节点的所有
key < key1，其中key1为node的第一个key的值。如果某个指针在节点node最右边且不为null，则其指向节点的所有
key ≥ keym，其中keym为node的最后一个key的值。如果某个指针在节点node的左右相邻key分别是keyi和keyi+1，则其指向节点的所有key满足：
keyi ≤ key < keyi+1。
但是，由于插入/删除数据记录会破坏B-Tree的性质，因此在插入/删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。
B+Tree
B-Tree有许多变种，其中最常见的是B+Tree。与B-Tree相比，B+Tree有以下不同点：
每个节点的指针上限为2d而不是2d+1；
内节点只存储key和指针，不存储data，叶子节点不存储指针，只存储key和data；
内节点：或内部节点，是指除去树最下面的叶子节点和根节点的其余节点；
子节点：对每个B+Tree的节点而言，其实都是由n个子节点组成的，比如2-3B-Tree（2-3树），每个节点只可能有 2 或 3 个子节点；
如下为B+Tree的示意图：
由于并不是所有节点都具有相同的域（指针/key/data），因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。
一般来说，B+Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关。
带有顺序访问指针的B+Tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
如上图所示：在B+Tree的基础之上，每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提高了区间查询效率。
内容来源
B-Tree和B+Tree，改正了两处不准确的地方，重画了图例。
Last updated
