概念
B+树是B树的扩展，是常用的数据库索引结构。
基本结构对比
在B树中，有如下特征：
- 所有节点都存放索引和数值（Key+Value）
- 叶子节点具有相同深度，叶节点的指针为空。
- 所有索引元素不重复。
1.png
而B+树中，有如下不同：
- 非叶子节点只存储索引（Key）,叶子节点存放所有索引和数值（Key+Value）。
- 叶子节点具有相同深度，并且叶子节点之间按照顺序通过指针连接。
- 部分索引会出现重复，有冗余。
2.png
B+树的优势
- 内部节点只存放索引，索引所占空间小，所以单个节点在相同存储空间下，比B树可以存放更多的索引（Key）。进而索引节点的子节点指针会更多（指向子节点出度会更大），或者说树结构会更宽，进而可以使树的深度更小。由于树的深度直接影响性能（时间复杂度和IO性能），所以B+树性能会更高。
- 叶子节点按顺序通过指针连接，当需要进行数据依次访问时，能极大提高效率。
- 维持树的平衡成本更低，因为数据都存在叶子节点上，所以都是从叶子节点进行更新/删除，比B树操作简单。
- 其他方面，更好利用外存存储（在其他笔记里面展开）
网友评论