B树（B-Tree）详解 - 为什么每个数据库都在使用它

if len(node.keys) >= self.order:  # 没有-1
    self._split_child(parent, index)

步骤1：读取根节点（1次磁盘I/O）
  键值：[50, 100, 150, ...]
  72在50和100之间
  跟随子节点指针2

步骤2：读取内部节点（1次磁盘I/O）
  键值：[55, 60, 65, 70, 75, 80, ...]
  72在70和75之间
  跟随子节点指针5

步骤3：读取叶子节点（1次磁盘I/O）
  键值：[71, 72, 73, 74]
  找到！返回键值72的值

总计：3次磁盘I/O操作 = HDD上30毫秒，SSD上0.3毫秒

from typing import List, Optional
from dataclasses import dataclass, field


@dataclass
class BTreeNode:
    """
    B树节点，存储键值和子节点指针。

    属性:
        keys: 该节点中排序后的键值列表
        children: 子节点指针列表（长度 = len(keys) + 1）
        is_leaf: 是否为叶子节点（无子节点）

    不变量:
        - len(children) == len(keys) + 1（对于内部节点）
        - 所有键值都是排序的
        - children[i]中的键 < keys[i] < children[i+1]中的键
    """
    keys: List[int] = field(default_factory=list)
    children: List['BTreeNode'] = field(default_factory=list)
    is_leaf: bool = True

    def __repr__(self):
        return f"BTreeNode(keys={self.keys}, is_leaf={self.is_leaf})"


class BTree:
    """
    B树实现，可配置阶数（最大子节点数）。

    属性:
        order: 每个节点的最大子节点数（扇出）
        root: 树的根节点

    属性:
        - 每个节点最多有 (order - 1) 个键
        - 每个非根节点至少有 (order // 2 - 1) 个键
        - 树高度是 O(log_order n)

    时间复杂度:
        - 查找: O(log n)
        - 插入: O(log n)
        - 删除: O(log n)

    空间复杂度: O(n)
    """

    def __init__(self, order: int = 100):
        """
        初始化B树。

        参数:
            order: 每个节点的最大子节点数（扇出）。
                   更高的阶数 = 更少的层数但更大的节点。
                   基于磁盘存储的典型值：100-1000。
        """
        if order < 3:
            raise ValueError("阶数必须至少为3")

        self.order = order
        self.root = BTreeNode()

    def search(self, key: int) -> Optional[int]:
        """
        在B树中搜索键值。

        参数:
            key: 要搜索的键值

        返回:
            如果找到返回键值，否则返回None

        时间复杂度: O(log n)，n为键的数量
        """
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node: BTreeNode, key: int) -> Optional[int]:
        """
        从节点开始递归搜索键值。

        使用节点内的二分查找找到正确的子节点。
        """
        # 节点内二分查找
        i = self._binary_search(node.keys, key)

        # 找到精确匹配
        if i < len(node.keys) and node.keys[i] == key:
            return key

        # 到达叶子节点但未找到
        if node.is_leaf:
            return None

        # 递归到适当的子节点
        # （实际实现中，这会是磁盘I/O）
        return self._search_recursive(node.children[i], key)

    def _binary_search(self, keys: List[int], key: int) -> int:
        """
        二分查找键值的插入位置。

        返回:
            索引i，使得keys[i-1] < key <= keys[i]

        时间复杂度: O(log m)，m为节点中的键数量
        """
        left, right = 0, len(keys)
        while left < right:
            mid = (left + right) // 2
            if keys[mid] < key:
                left = mid + 1
            else:
                right = mid
        return left

    def insert(self, key: int):
        """
        向B树插入键值。

        参数:
            key: 要插入的键值

        时间复杂度: O(log n)

        算法:
            1. 找到合适的叶子节点
            2. 将键值插入叶子
            3. 如果叶子溢出（键值太多），分裂它
            4. 如果需要，将分裂向上传播
        """
        root = self.root

        # 如果根节点满了，分裂它并创建新根
        if len(root.keys) >= self.order - 1:
            new_root = BTreeNode(is_leaf=False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root

        self._insert_non_full(self.root, key)

    def _insert_non_full(self, node: BTreeNode, key: int):
        """
        向未满的节点插入键值。

        递归地找到正确的叶子节点并插入。
        """
        i = len(node.keys) - 1

        if node.is_leaf:
            # 插入到排序位置
            node.keys.append(None)  # 腾出空间
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            # 找到要插入的子节点
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1

            # 如果子节点满了，先分裂它
            if len(node.children[i].keys) >= self.order - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1

            self._insert_non_full(node.children[i], key)

    def _split_child(self, parent: BTreeNode, child_index: int):
        """
        分裂满的子节点为两个节点。

        参数:
            parent: 包含满子节点的父节点
            child_index: 满子节点在父节点children中的索引

        算法:
            1. 创建新的兄弟节点
            2. 将满子节点的一半键值移动到兄弟节点
            3. 将中间键值提升到父节点
            4. 更新父节点的子节点列表
        """
        full_child = parent.children[child_index]
        new_sibling = BTreeNode(is_leaf=full_child.is_leaf)

        mid = (self.order - 1) // 2

        # 将一半键值移动到新兄弟节点
        new_sibling.keys = full_child.keys[mid + 1:]
        full_child.keys = full_child.keys[:mid]

        # 如果不是叶子节点，移动一半子节点
        if not full_child.is_leaf:
            new_sibling.children = full_child.children[mid + 1:]
            full_child.children = full_child.children[:mid + 1]

        # 将中间键值提升到父节点
        promoted_key = full_child.keys[mid]
        parent.keys.insert(child_index, promoted_key)
        parent.children.insert(child_index + 1, new_sibling)

    def print_tree(self, node: Optional[BTreeNode] = None, level: int = 0):
        """
        打印树结构用于调试。
        """
        if node is None:
            node = self.root

        print("  " * level + f"Level {level}: {node.keys}")
        if not node.is_leaf:
            for child in node.children:
                self.print_tree(child, level + 1)


# 使用示例
if __name__ == "__main__":
    # 创建阶数为5的B树（每个节点最多4个键）
    btree = BTree(order=5)

    # 插入键值
    keys = [10, 20, 5, 6, 12, 30, 7, 17, 3, 16, 21, 24, 25, 26, 27]
    print("插入键值:", keys)
    for key in keys:
        btree.insert(key)

    print("\nB树结构:")
    btree.print_tree()

    # 搜索键值
    print("\n搜索键值:")
    for search_key in [6, 16, 21, 100]:
        result = btree.search(search_key)
        if result:
            print(f"  键 {search_key}: 找到")
        else:
            print(f"  键 {search_key}: 未找到")

插入键值: [10, 20, 5, 6, 12, 30, 7, 17, 3, 16, 21, 24, 25, 26, 27]

B树结构:
Level 0: [12, 20, 25]
  Level 1: [3, 5, 6, 7, 10]
  Level 1: [16, 17]
  Level 1: [21, 24]
  Level 1: [26, 27, 30]

搜索键值:
  键 6: 找到
  键 16: 找到
  键 21: 找到
  键 100: 未找到

-- 创建带主键的表
CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100)
) ENGINE=InnoDB;

-- 主键自动创建聚簇B+树索引
-- 叶子节点包含实际行数据
-- 树结构：id=1与name和email一起存储在叶子中

-- 在email上创建二级索引
CREATE INDEX idx_email ON users(email);

-- 二级索引是单独的B+树
-- 叶子节点包含email → id映射
-- 要获取完整行：在idx_email中查找email → 获取id → 查找主键中的id

-- 快速：索引列上的范围查询
SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31';
-- B树顺序遍历叶子节点（叶子节点是链接的）

-- 慢：非索引列上的范围查询
SELECT * FROM orders WHERE total_amount BETWEEN 100 AND 200;
-- 必须扫描整个表（total_amount上没有索引）