B+树
介绍
B+树是一种平衡树数据结构,是B树的变种,被广泛应用于数据库索引和文件系统中。B+树保持数据有序,而且能够高效地进行查找、顺序访问、插入和删除操作。
B+树的主要组成部分包括:
- 节点:B+树中的基本单元,分为内部节点和叶子节点
- 内部节点:只存储键值和指向子节点的指针,不存储数据
- 叶子节点:存储键值和真实数据(或指向数据的指针)
- 阶数(order):表示一个节点最多可以有多少个子节点,通常用m表示
- 链表:所有叶子节点形成一个有序链表,方便范围查询
面试鸭上也有很多关于 B+ 树的内容:https://www.mianshiya.com/search/all?searchText=B%2B%E6%A0%91
核心特性
- 所有数据都存储在叶子节点上:内部节点只存储键值和指针,不存储实际数据
- 所有叶子节点通过指针连接成有序链表:便于范围查询和顺序遍历
- 平衡树结构:所有叶子节点到根节点的距离相同
- 高扇出性(High Fan-out):每个节点可以包含多个键值和指针,减少树的高度
...