【数据基础】— B树
目录
B树（B-tree）
定义与特性
结构与规则
操作
B+树
定义与特性
结构与规则
操作
B+树的优势
B树（B-tree）
定义与特性
- B树是一种自平衡的树状数据结构，能够保持数据有序。在计算机科学中，B树被广泛应用于数据库和文件系统的实现中，以优化大块数据的读写操作。
- B树是一个多路查找树，可以拥有多于2个子节点，这使得它相对于传统的二叉查找树在存储和查找大量数据时更加高效。
- B树通过减少定位记录时所经历的中间过程来加快存取速度，其查找、插入和删除操作的时间复杂度均为对数时间。
结构与规则
- B树中的每个节点至多有m个子节点（m>=2），且通常含有m-1个关键字。
- 除非根节点是叶子节点，否则每个节点至少有m/2个子节点。
- 节点中的关键字按照升序排列，且每个关键字都代表其子树中所有记录的最大或最小值。
- 所有叶子节点都在同一层上，且通常不包含实际数据，而是作为查找路径的终点。
操作
- 查找：从根节点开始，根据关键字与节点内关键字的比较结果选择子节点进行递归查找，直到找到目标记录或到达叶子节点。
- 插入：新记录总是插入到最底层的叶子节点中。如果插入后节点关键字个数超过上限，则需要进行节点分裂和父节点关键字的调整。
- 删除：删除操作也发生在叶子节点上。如果删除后节点关键字个数低于下限，则需要进行节点合并或向兄弟节点借关键字等操作来保持树的平衡。
B+树
定义与特性
B+树（B+ Tree）是一种自平衡的树状数据结构，它是B树（B-Tree）的一种变体，但在结构上进行了优化，特别适用于数据库和操作系统的文件系统中。B+树的所有数据都存储在叶子节点中，且叶子节点之间通过指针相连形成链表，这使得它在进行范围查询和顺序访问时非常高效。
结构与规则
- 节点类型：B+树包含根节点、内部节点和叶子节点。
- 根节点：可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。
- 内部节点：仅包含其子树（或根节点）中的最大（或最小）关键字作为索引，不存储实际数据。
- 叶子节点：包含全部关键字的信息及指向含有这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
- 节点容量：
- 假设B+树为m阶，则每个节点至多有m个子节点（或关键字）。
- 除根节点外，每个节点至少有m/2个子节点（或关键字）。
- 叶子节点都位于同一层，确保了树的高度平衡。
- 关键字与指针：
- 内部节点中的关键字仅用于索引，不存储实际数据。
- 叶子节点包含全部关键字的信息及指向记录的指针，支持直接访问数据。
- 叶子节点之间通过指针相连，形成有序链表，支持高效的顺序访问和范围查询。
操作
- 查找：
- 从根节点开始，根据关键字与节点内关键字的比较结果选择子节点进行递归查找。
- 当到达叶子节点时，根据关键字找到对应的记录或确认查找失败。
- B+树的查找效率较高，因为所有实际数据都存储在叶子节点中，且叶子节点之间通过指针相连。
- 插入：
- 新记录总是插入到叶子节点中。
- 如果插入后叶子节点关键字个数超过上限（m），则进行节点分裂，并将新的关键字提升到父节点中。
- 如果父节点也因此变得过满，则继续向上分裂，直到根节点或创建一个新的根节点为止。
- 删除：
- 删除操作也发生在叶子节点上。
- 如果删除后叶子节点关键字个数低于下限（m/2-1），则需要进行节点合并或向兄弟节点借关键字等操作来保持树的平衡。
- 如果合并或借关键字导致父节点关键字个数也低于下限，则继续向上调整直到根节点或达到平衡状态为止。
B+树的优势
- 范围查询和顺序访问高效：由于叶子节点之间通过指针相连形成链表，B+树在进行范围查询和顺序访问时非常高效。
- 磁盘读写次数少：由于非叶子节点仅包含索引信息而不存储实际数据，因此可以一次性读入更多的索引信息到内存中，减少了磁盘读写次数。
- 稳定性好：B+树的插入、删除和查找操作都遵循稳定的对数时间复杂度，保证了数据操作的稳定性和效率。