B+树是数据库中常用的一种多层级索引（在密集索引上层增加了松散索引）数据结构，B代表了balanced，即对于索引树中的所有节点，包括叶子的和非叶子的，它们存储的索引条目和指针数量是均衡的；使得树的层级较低，而检索每一个条目所走的从根到叶子的路径长度是相同的。
B树是在B+树的基础上加了一层限制：所有节点存储的条目不能有冗余。这种结构对于数据的检索，有可能带来性能的提升，但是会给索引的维护（即插入和删除）性能带来明显的下降。在很多论文和书籍里会提到B树，其实指的是B+树，这是一种习惯叫法。具体要看文中的语境。
B+树具体的结构可以这样来描述：对于一张表的记录，在检索键key上创建一个B+树索引，在索引的所有节点里，包含至多n-1个search-key value(键值)和至多n个指针，n的值基于具体的算法而定。下面具体地来看节点的结构，首先在索引的叶子块中，存有key这个键对应的所有的value；指向对应key=value的记录的指针；指向下一个叶子块的指针。如图所示，k1..kn-1代表n-1个键值，p1..pn-1是对应键值所在记录的指针，pn是指向下一个叶子块的指针。叶子块中的键值数目，要大于等于ceil((n-1)/2)。
其次，索引的非叶子块结构与叶子块类似，区别在于指针指向的是索引中的节点；并且指针的数量在ceil(n/2)与n之间。对于非叶子节点，第i个指针pi，指向的是包含[ki-1, ki)范围键值的节点。
下面是一个索引结构的例子。
表中数据如右下角所示，表的4个列分别是id, name, department和salary。索引创建在name列上。这里n=4.
当要查询name=kim的记录时，从root的第一个value开始检索，直到满足kim<=Ki; 如果不存在这样的value，那么取最后一个指针，并访问该指针指向的节点；如果存在这样的value Ki满足kim=Ki, 那么取指针Pi+1并访问指针指向的节点；剩下的情况就是，存在value Ki满足kim<Ki, 那么就取指针Pi。
检索internal node的方式与前面类似，最终定位到Kim可能所在的叶子节点。然后在叶子节点中检索,直到找到Kim所在的位置i,返回指针Pi；或者在该节点搜索穷尽后，也找不到Kim，则返回找不到该值。
下图是一个B树索引的例子：
B-tree
所有的键值在索引的节点中只出现一次，这样就必须在非叶子结点中，增加指向表记录的指针。比如上图中的root,存有3个键值；第一个指针指向第一个叶子块，第二个指针指向Einstein对应的表记录或者存有记录地址的bucket（当有多条记录时）。这样的结构，节省了索引所占的些许空间，查询也会有一点点性能提升（查询在非叶子结点中存储的键值时，比B+树少扫描几个block），但是维护的成本很高：删除某个键值时，如果该键值在非叶子结点里，需要从子节点中找到合适的值来填充进来；这样也可能导致子节点含有的键值过少，从而引发子节点的合并或者重分配。相较之下，大多数数据库系统采用了B+树结构，而不是B树，尽管仍然描述为B树索引。
网友评论