数据库索引原理

// B+Tree 节点结构（概念）
interface BPlusTreeNode {
  isLeaf: boolean
  keys: Key[]           // 索引键
  children: Node[]      // 非叶子节点：子节点指针
  values: Value[]       // 叶子节点：数据或行指针
  next: LeafNode | null // 叶子节点：下一个叶子
}

// 16KB 页能存储的键数量
// 假设键 8 字节、指针 6 字节
// 非叶子节点：16384 / 14 ≈ 1170 个键
// 3 层 B+Tree：1170 * 1170 * 1170 ≈ 16 亿行

// 查询过程（伪代码）
function search(key: Key): Value | null {
  let node = this.root
  
  // 从根节点向下搜索
  while (!node.isLeaf) {
    // 二分查找子节点指针
    const index = binarySearch(node.keys, key)
    node = node.children[index]  // 1 次磁盘 IO
  }
  
  // 在叶子节点查找
  const index = binarySearch(node.keys, key)
  return node.keys[index] === key ? node.values[index] : null
}

// 范围查询利用叶子链表
function rangeSearch(startKey: Key, endKey: Key): Value[] {
  let node = this.findLeaf(startKey)
  const results: Value[] = []
  
  while (node && node.keys[0] <= endKey) {
    for (let i = 0; i < node.keys.length; i++) {
      if (node.keys[i] >= startKey && node.keys[i] <= endKey) {
        results.push(node.values[i])
      }
    }
    node = node.next  // 沿链表遍历
  }
  return results
}