B+树结构

概念

B+树是B树的扩展，是常用的数据库索引结构。

基本结构对比

在B树中，有如下特征：

• 所有节点都存放索引和数值（Key+Value）
• 叶子节点具有相同深度，叶节点的指针为空。
• 所有索引元素不重复。

1.png

而B+树中，有如下不同：

• 非叶子节点只存储索引（Key）,叶子节点存放所有索引和数值（Key+Value）。
• 叶子节点具有相同深度，并且叶子节点之间按照顺序通过指针连接。
• 部分索引会出现重复，有冗余。

2.png

B+树的优势

• 内部节点只存放索引，索引所占空间小，所以单个节点在相同存储空间下，比B树可以存放更多的索引（Key）。进而索引节点的子节点指针会更多（指向子节点出度会更大），或者说树结构会更宽，进而可以使树的深度更小。由于树的深度直接影响性能（时间复杂度和IO性能），所以B+树性能会更高。
• 叶子节点按顺序通过指针连接，当需要进行数据依次访问时，能极大提高效率。
• 维持树的平衡成本更低，因为数据都存在叶子节点上，所以都是从叶子节点进行更新/删除，比B树操作简单。
• 其他方面，更好利用外存存储（在其他笔记里面展开）