Btree 树

B-tree（B树）是一种常见的 多路平衡查找树（balanced search tree），广泛应用于 数据库索引（如MySQL、PostgreSQL） 和 文件系统（如NTFS、HFS+） 中，用于高效地存储和检索大量数据。

在理解 B树之前，首先要明白计算机存储的层次结构：

数据库的表数据通常远远大于可用内存，因此必须存储在磁盘上。磁盘I/O（即从磁盘读取数据到内存）是数据库操作中最耗时的部分。

B树的核心设计目标就是最大限度地减少磁盘I/O次数。

二叉搜索树的缺陷：一个节点只存一个键和两个指针。如果数据量巨大，树会变得非常高。每次比较都可能需要一次新的磁盘I/O，效率极低。
B树的优势：B树的一个节点可以存储大量键值和指针。这意味着树的高度非常低（通常只有3-4层），从而使得在十亿级别的数据中查找一个记录，也仅需3-4次磁盘I/O。

一棵 m 阶 B 树（m-way B-tree） 具有以下性质：

节点类型：
- 内部节点：存储若干键（key）、对应的数据记录或数据指针，以及指向子节点的指针。
  （与 B+ 树不同，B 树的内部节点也可以存放实际数据。）
- 叶子节点：存储键和对应的数据（或指向数据的指针）。
  所有叶子节点都位于同一层，体现了树的平衡性。
键的数量：
- 除根节点外，每个节点至少包含 ⌈m/2⌉ − 1 个键，最多包含 m − 1 个键。
- 根节点至少包含 1 个键（若它不是叶节点）。
子节点数量：
- 若一个内部节点有 k 个键，则它恰好有 k + 1 个子节点。
- 每个子节点也是一棵 B 树。
键的排序与子树范围：
- 每个节点中的键按照**非降序（通常为升序）**排列。
- 对于一个节点中键 K₁, K₂, ..., Kₖ：
  - 第 1 个子树中所有键 < K₁
  - 第 2 个子树中所有键 ∈ (K₁, K₂)
  - …
  - 第 (k+1) 个子树中所有键 > Kₖ

B 树的查找操作与二叉搜索树类似，但在每个节点中是多路分支查找，即每个节点可以包含多个键值和多个子指针。
与 B+ 树不同的是，B 树的键和值（数据或数据指针）都可能存在于内部节点或叶子节点中。

查找过程：

从根节点开始。
如果根节点为空，则查找失败。
在当前节点中查找目标键：
- 在节点的键集合中进行顺序查找或二分查找；
- 如果在当前节点中找到目标键，则查找成功（可直接返回该节点中的数据或数据指针）；
- 如果未找到目标键，则确定目标键位于哪两个键之间，从而选取对应的子节点指针。
访问子节点。
根据指针找到对应的子节点（通常对应磁盘页），并将其读入内存。
重复步骤 2 和 3，
直到：
- 找到目标键（查找成功），或
- 到达叶子节点仍未找到（查找失败）。

示例：在下图的 3 阶 B 树中查找键 15：

        [10, 20]
       /    |     \
 [5, 8]  [13, 15, 18]  [25, 30]

查找过程：

插入操作比查找复杂，因为它可能破坏B树的定义（如节点键数超过m-1），因此可能需要分裂节点。

过程：

示例：向一个 3 阶 B 树（m=3，每个节点最多 2 个键）中插入 25。

初始状态：

        [10]
       /    \
     [5]    [20, 30]   <-- 要插入到这里

最终状态：

        [10, 25]
        /   |   \
      [5]  [20] [30]

在实际的数据库系统中（如MySQL的InnoDB引擎），更常用的是B树的变种——B+树。它与B树的主要区别在于：

特性	B树	B+树
数据存储	内部节点和叶子节点都存储数据指针。	只有叶子节点存储数据指针（或完整的数据记录）。内部节点只存储键和子节点指针。
叶子节点链接	叶子节点之间没有链接。	所有叶子节点通过一个链表串联起来。
查询性能	可能在内部节点就找到数据，提前返回。	任何查找都必须到达叶子节点。
范围查询	效率较低，需要回溯。	效率极高。一旦在叶子节点找到起点，顺着链表扫描即可。
内部节点扇出	由于存储数据指针，每个节点能存的键相对较少。	不存储数据指针，所以每个节点能存更多的键，树更矮胖。

B+树是现代关系型数据库索引的绝对主流实现方式。

B树是一种为磁盘存储量身定做的、多路的、自平衡的搜索树。它通过最大化每个节点的容量来最小化树的高度，从而将昂贵的磁盘I/O次数降到最低，是数据库和文件系统能够高效管理海量数据的基石。其变种B+树则进一步优化了范围查询和顺序访问的性能，成为了数据库索引的实际标准。