核心原理

B-Tree是一种自平衡的多路搜索树，专为磁盘存储优化。它的核心特征：

1. 有序存储：键值按序存储，支持高效范围查询
2. 就地更新：更新操作直接修改磁盘上的页面
3. 平衡保证：所有叶子节点在同一层，保证O(log n)性能
4. 高扇出：每个节点可以有多个子节点（通常几百个），减少树的高度

B-Tree的实现细节

// B-Tree节点结构（简化版）
interface BTreeNode<K, V> {
  isLeaf: boolean;
  keys: K[];  // 有序的键数组
  values?: V[];  // 叶子节点存储值
  children?: BTreeNode<K, V>[];  // 内部节点存储子节点指针
  parent?: BTreeNode<K, V>;
}

class BTree<K, V> {
  private root: BTreeNode<K, V>;
  private readonly order: number;  // B-Tree的阶（最大子节点数）
  private readonly minKeys: number;  // 最小键数 = ceil(order/2) - 1
  private readonly maxKeys: number;  // 最大键数 = order - 1

  constructor(order: number = 128) {
    this.order = order;
    this.minKeys = Math.ceil(order / 2) - 1;
    this.maxKeys = order - 1;
    this.root = this.createLeafNode();
  }

  private createLeafNode(): BTreeNode<K, V> {
    return {
      isLeaf: true,
      keys: [],
      values: [],
    };
  }

  private createInternalNode(): BTreeNode<K, V> {
    return {
      isLeaf: false,
      keys: [],
      children: [],
    };
  }

  // 查找操作：O(log n)
  search(key: K): V | undefined {
    return this.searchNode(this.root, key);
  }

  private searchNode(node: BTreeNode<K, V>, key: K): V | undefined {
    // 在节点的键数组中二分查找
    let i = 0;
    while (i < node.keys.length && key > node.keys[i]) {
      i++;
    }

    // 找到精确匹配
    if (i < node.keys.length && key === node.keys[i]) {
      return node.isLeaf ? node.values![i] : this.searchNode(node.children![i + 1], key);
    }

    // 如果是叶子节点，键不存在
    if (node.isLeaf) {
      return undefined;
    }

    // 递归到子节点
    return this.searchNode(node.children![i], key);
  }

  // 插入操作：可能触发节点分裂
  insert(key: K, value: V): void {
    const root = this.root;

    // 如果根节点已满，需要分裂根节点
    if (root.keys.length === this.maxKeys) {
      const newRoot = this.createInternalNode();
      newRoot.children = [root];
      this.splitChild(newRoot, 0);
      this.root = newRoot;
      this.insertNonFull(newRoot, key, value);
    } else {
      this.insertNonFull(root, key, value);
    }
  }

  private insertNonFull(node: BTreeNode<K, V>, key: K, value: V): void {
    let i = node.keys.length - 1;

    if (node.isLeaf) {
      // 叶子节点：直接插入
      node.keys.push(key);
      node.values!.push(value);
      
      // 保持有序
      while (i >= 0 && key < node.keys[i]) {
        node.keys[i + 1] = node.keys[i];
        node.values![i + 1] = node.values![i];
        i--;
      }
      node.keys[i + 1] = key;
      node.values![i + 1] = value;
    } else {
      // 内部节点：找到合适的子节点
      while (i >= 0 && key < node.keys[i]) {
        i--;
      }
      i++;

      // 如果子节点已满，先分裂
      if (node.children![i].keys.length === this.maxKeys) {
        this.splitChild(node, i);
        if (key > node.keys[i]) {
          i++;
        }
      }
      this.insertNonFull(node.children![i], key, value);
    }
  }

  // 分裂满节点
  private splitChild(parent: BTreeNode<K, V>, index: number): void {
    const fullChild = parent.children![index];
    const newChild: BTreeNode<K, V> = fullChild.isLeaf 
      ? this.createLeafNode() 
      : this.createInternalNode();

    const midIndex = Math.floor(this.maxKeys / 2);

    // 将中间键提升到父节点
    const midKey = fullChild.keys[midIndex];
    parent.keys.splice(index, 0, midKey);
    parent.children!.splice(index + 1, 0, newChild);

    // 分配键到新节点
    newChild.keys = fullChild.keys.splice(midIndex + 1);
    fullChild.keys.length = midIndex;

    if (fullChild.isLeaf) {
      newChild.values = fullChild.values!.splice(midIndex + 1);
      fullChild.values!.length = midIndex;
    } else {
      newChild.children = fullChild.children!.splice(midIndex + 1);
      fullChild.children!.length = midIndex + 1;
    }
  }

  // 范围查询：B-Tree的优势
  range(start: K, end: K): [K, V][] {
    const results: [K, V][] = [];
    this.rangeSearch(this.root, start, end, results);
    return results;
  }

  private rangeSearch(
    node: BTreeNode<K, V>,
    start: K,
    end: K,
    results: [K, V][]
  ): void {
    let i = 0;
    while (i < node.keys.length && start > node.keys[i]) {
      i++;
    }

    while (i < node.keys.length && node.keys[i] <= end) {
      if (!node.isLeaf) {
        this.rangeSearch(node.children![i], start, end, results);
      }

      if (node.keys[i] >= start && node.keys[i] <= end) {
        if (node.isLeaf) {
          results.push([node.keys[i], node.values![i]]);
        }
      }
      i++;
    }

    if (!node.isLeaf && i < node.children!.length) {
      this.rangeSearch(node.children![i], start, end, results);
    }
  }
}

B-Tree的性能特征

// 单点查询：需要读取 O(log_B N) 个页面
// 其中 B 是节点的扇出（通常很大，如256）
// 对于10亿条记录，可能只需要3-4次磁盘I/O

interface ReadAmplification {
  pointQuery: number;  // log_B(N)
  rangeQuery: number;  // log_B(N) + 范围大小/页面大小
}

// 示例计算
function calculateBTreeReads(totalKeys: number, fanout: number): ReadAmplification {
  const treeHeight = Math.ceil(Math.log(totalKeys) / Math.log(fanout));
  
  return {
    pointQuery: treeHeight,  // 从根到叶的路径
    rangeQuery: treeHeight,  // 加上连续的叶子节点扫描
  };
}

console.log(calculateBTreeReads(1_000_000_000, 256));
// { pointQuery: 4, rangeQuery: 4 + 范围扫描 }

interface WriteAmplification {
  logical: number;  // 逻辑写入量
  physical: number;  // 实际物理写入量
  amplification: number;  // 放大倍数
}

// B-Tree写入示例
function btreeWriteAmplification(keySize: number, valueSize: number, pageSize: number): WriteAmplification {
  const entrySize = keySize + valueSize;
  const logical = entrySize;
  
  // 最坏情况：更新一个叶子节点页面 + 可能的分裂
  // 平均情况：约1.5个页面（考虑偶尔的分裂）
  const physical = pageSize * 1.5;
  
  return {
    logical,
    physical,
    amplification: physical / logical,
  };
}

console.log(btreeWriteAmplification(8, 100, 4096));
// 写放大约 50-60x

核心原理

LSM-Tree通过将随机写转化为顺序写来优化写性能，其核心思想：

1. 内存缓冲（MemTable）：所有写入先进入内存中的有序结构
2. 不可变SSTable：内存满时刷盘为不可变的Sorted String Table
3. 分层组织：SSTable组织为多层，每层大小递增
4. 后台合并（Compaction）：定期合并SSTable，清理过期数据

// LSM-Tree整体架构
interface LSMTree<K, V> {
  memTable: MemTable<K, V>;  // 当前活跃的内存表
  immutableMemTables: MemTable<K, V>[];  // 等待刷盘的不可变内存表
  levels: Level[];  // 磁盘上的分层SSTable
  writeAheadLog: WAL;  // Write-Ahead Log，用于崩溃恢复
}

// 内存表：通常使用跳表或红黑树
class MemTable<K, V> {
  private skipList: SkipList<K, V>;
  private size: number = 0;
  private readonly maxSize: number;

  constructor(maxSize: number = 64 * 1024 * 1024) {  // 64MB
    this.skipList = new SkipList();
    this.maxSize = maxSize;
  }

  put(key: K, value: V): boolean {
    this.skipList.insert(key, value);
    this.size += this.estimateSize(key, value);
    return this.size >= this.maxSize;
  }

  get(key: K): V | undefined {
    return this.skipList.search(key);
  }

  private estimateSize(key: K, value: V): number {
    // 估算键值对的内存占用
    return JSON.stringify(key).length + JSON.stringify(value).length + 32;  // 加上开销
  }

  // 转换为不可变的有序数组（用于刷盘）
  freeze(): [K, V][] {
    return this.skipList.toArray();
  }
}

// SSTable（Sorted String Table）
interface SSTable {
  fileId: string;
  level: number;
  minKey: string;
  maxKey: string;
  numEntries: number;
  fileSize: number;
  bloomFilter: BloomFilter;  // 布隆过滤器，加速查找
  indexBlock: IndexBlock;  // 索引块，快速定位数据块
}

// 分层结构
interface Level {
  level: number;
  sstables: SSTable[];
  totalSize: number;
  maxSize: number;  // Level N 的最大大小：10^N MB
}

LSM-Tree的写入路径

class LSMTreeImpl<K extends string, V> {
  private memTable: MemTable<K, V>;
  private immutableMemTables: MemTable<K, V>[] = [];
  private levels: Level[] = [];
  private wal: WAL;

  constructor() {
    this.memTable = new MemTable();
    this.wal = new WAL("wal.log");
    this.initializeLevels();
  }

  private initializeLevels(): void {
    // 初始化7层：L0=10MB, L1=100MB, L2=1GB, ...
    for (let i = 0; i < 7; i++) {
      this.levels.push({
        level: i,
        sstables: [],
        totalSize: 0,
        maxSize: 10 * Math.pow(10, i) * 1024 * 1024,  // 10 * 10^i MB
      });
    }
  }

  // 写入操作：O(log n) in memory
  async put(key: K, value: V): Promise<void> {
    // 1. 先写WAL（保证持久性）
    await this.wal.append({ type: "PUT", key, value });

    // 2. 写入MemTable
    const shouldFlush = this.memTable.put(key, value);

    // 3. 如果MemTable满了，触发刷盘
    if (shouldFlush) {
      await this.flushMemTable();
    }
  }

  // 刷盘：将MemTable转换为SSTable
  private async flushMemTable(): Promise<void> {
    // 1. 冻结当前MemTable
    const frozenMemTable = this.memTable;
    this.immutableMemTables.push(frozenMemTable);

    // 2. 创建新的MemTable
    this.memTable = new MemTable();

    // 3. 异步刷盘（不阻塞写入）
    const entries = frozenMemTable.freeze();
    const sstable = await this.writeSSTable(entries, 0);

    // 4. 添加到Level 0
    this.levels[0].sstables.push(sstable);
    this.levels[0].totalSize += sstable.fileSize;

    // 5. 检查是否需要Compaction
    if (this.levels[0].totalSize > this.levels[0].maxSize) {
      await this.compact(0);
    }

    // 6. 移除已刷盘的不可变MemTable
    this.immutableMemTables.shift();
  }

  // 写入SSTable文件
  private async writeSSTable(entries: [K, V][], level: number): Promise<SSTable> {
    const fileId = `L${level}-${Date.now()}-${Math.random().toString(36).slice(2)}.sst`;
    const bloomFilter = new BloomFilter(entries.length, 0.01);  // 1% 误报率
    const indexBlock: IndexBlock = { offsets: [] };

    // 写入数据块（按块组织，每块4KB）
    const BLOCK_SIZE = 4096;
    let currentBlock: [K, V][] = [];
    let currentBlockSize = 0;
    let offset = 0;

    for (const [key, value] of entries) {
      // 添加到布隆过滤器
      bloomFilter.add(key);

      const entrySize = key.length + JSON.stringify(value).length;
      
      if (currentBlockSize + entrySize > BLOCK_SIZE && currentBlock.length > 0) {
        // 当前块已满，写入磁盘
        await this.writeBlock(fileId, currentBlock, offset);
        indexBlock.offsets.push({ key: currentBlock[0][0], offset });
        
        offset += currentBlockSize;
        currentBlock = [];
        currentBlockSize = 0;
      }

      currentBlock.push([key, value]);
      currentBlockSize += entrySize;
    }

    // 写入最后一个块
    if (currentBlock.length > 0) {
      await this.writeBlock(fileId, currentBlock, offset);
      indexBlock.offsets.push({ key: currentBlock[0][0], offset });
      offset += currentBlockSize;
    }

    return {
      fileId,
      level,
      minKey: entries[0][0],
      maxKey: entries[entries.length - 1][0],
      numEntries: entries.length,
      fileSize: offset,
      bloomFilter,
      indexBlock,
    };
  }

  private async writeBlock(fileId: string, block: [K, V][], offset: number): Promise<void> {
    // 实际的磁盘写入（简化）
    const data = JSON.stringify(block);
    // await fs.writeFile(fileId, data, { flag: 'a' });
  }
}

LSM-Tree的读取路径

class LSMTreeImpl<K extends string, V> {
  // ... 前面的代码 ...

  // 读取操作：需要查找多个层级
  async get(key: K): Promise<V | undefined> {
    // 1. 先查MemTable（最新数据）
    const memValue = this.memTable.get(key);
    if (memValue !== undefined) {
      return memValue;
    }

    // 2. 查不可变MemTable（从新到旧）
    for (const immMemTable of this.immutableMemTables) {
      const value = immMemTable.get(key);
      if (value !== undefined) {
        return value;
      }
    }

    // 3. 查磁盘SSTable（从L0到L6）
    for (const level of this.levels) {
      const value = await this.searchLevel(level, key);
      if (value !== undefined) {
        return value;
      }
    }

    return undefined;
  }

  private async searchLevel(level: Level, key: K): Promise<V | undefined> {
    // Level 0: SSTable可能重叠，需要查所有文件
    if (level.level === 0) {
      // 从新到旧查找
      for (let i = level.sstables.length - 1; i >= 0; i--) {
        const value = await this.searchSSTable(level.sstables[i], key);
        if (value !== undefined) {
          return value;
        }
      }
      return undefined;
    }

    // Level 1+: SSTable不重叠，二分查找
    const sstableIndex = this.binarySearchSSTable(level.sstables, key);
    if (sstableIndex === -1) {
      return undefined;
    }

    return await this.searchSSTable(level.sstables[sstableIndex], key);
  }

  private binarySearchSSTable(sstables: SSTable[], key: K): number {
    let left = 0;
    let right = sstables.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      const sst = sstables[mid];

      if (key < sst.minKey) {
        right = mid - 1;
      } else if (key > sst.maxKey) {
        left = mid + 1;
      } else {
        return mid;  // key在这个SSTable的范围内
      }
    }

    return -1;
  }

  private async searchSSTable(sst: SSTable, key: K): Promise<V | undefined> {
    // 1. 布隆过滤器快速判断（可能存在）
    if (!sst.bloomFilter.mightContain(key)) {
      return undefined;  // 确定不存在
    }

    // 2. 使用索引块定位数据块
    const blockOffset = this.findBlockOffset(sst.indexBlock, key);
    if (blockOffset === -1) {
      return undefined;
    }

    // 3. 读取数据块并查找
    const block = await this.readBlock(sst.fileId, blockOffset);
    return this.searchBlock(block, key);
  }

  private findBlockOffset(indexBlock: IndexBlock, key: K): number {
    // 在索引块中二分查找
    const offsets = indexBlock.offsets;
    for (let i = 0; i < offsets.length; i++) {
      if (i === offsets.length - 1 || key < offsets[i + 1].key) {
        return offsets[i].offset;
      }
    }
    return -1;
  }

  private async readBlock(fileId: string, offset: number): Promise<[K, V][]> {
    // 实际的磁盘读取（简化）
    // const data = await fs.readFile(fileId);
    // return JSON.parse(data.toString());
    return [];
  }

  private searchBlock(block: [K, V][], key: K): V | undefined {
    // 块内二分查找
    let left = 0;
    let right = block.length - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (block[mid][0] === key) {
        return block[mid][1];
      } else if (block[mid][0] < key) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return undefined;
  }
}

LSM-Tree的读放大问题

LSM-Tree的读取需要查找多个层级，导致显著的读放大：

interface LSMReadAmplification {
  memTableReads: number;
  level0Reads: number;  // L0可能有多个重叠的SSTable
  otherLevelReads: number;  // L1-L6每层最多1个SSTable
  totalReads: number;
}

function calculateLSMReadAmplification(
  numLevel0SSTables: number,
  numLevels: number
): LSMReadAmplification {
  return {
    memTableReads: 1,
    level0Reads: numLevel0SSTables,  // 最坏情况：所有L0文件
    otherLevelReads: numLevels - 1,  // L1-L6各读1个
    totalReads: 1 + numLevel0SSTables + (numLevels - 1),
  };
}

console.log(calculateLSMReadAmplification(10, 7));
// { memTableReads: 1, level0Reads: 10, otherLevelReads: 6, totalReads: 17 }
// 读放大可能高达 10-20x！

Leveled Compaction（LevelDB/RocksDB默认策略）

class LSMTreeImpl<K extends string, V> {
  // ... 前面的代码 ...

  // Leveled Compaction
  private async compact(level: number): Promise<void> {
    if (level >= this.levels.length - 1) {
      return;  // 最后一层不需要compaction
    }

    const currentLevel = this.levels[level];
    const nextLevel = this.levels[level + 1];

    console.log(`Compacting L${level} -> L${level + 1}`);

    // 1. 选择要合并的SSTable
    const toCompact = this.selectFilesForCompaction(currentLevel);

    // 2. 找出下一层中与这些文件重叠的SSTable
    const overlapping = this.findOverlappingFiles(nextLevel, toCompact);

    // 3. 执行多路归并排序
    const merged = await this.mergeSSTablesConst mergedEntries: [K, V][] = [];
    const allFiles = [...toCompact, ...overlapping];

    // 使用优先队列进行K路归并
    const heap = new MinHeap<{ key: K; value: V; fileIndex: number }>();
    const iterators = allFiles.map(f => this.createSSTableIterator(f));

    // 初始化堆
    for (let i = 0; i < iterators.length; i++) {
      const first = await iterators[i].next();
      if (first) {
        heap.insert({ ...first, fileIndex: i });
      }
    }

    let lastKey: K | null = null;

    // 归并过程
    while (!heap.isEmpty()) {
      const min = heap.extractMin()!;

      // 去重：同一个key只保留最新的值
      if (lastKey === null || min.key !== lastKey) {
        // 检查是否是墓碑（删除标记）
        if (min.value !== null) {
          mergedEntries.push([min.key, min.value]);
        }
        lastKey = min.key;
      }

      // 从同一个文件读取下一个entry
      const next = await iterators[min.fileIndex].next();
      if (next) {
        heap.insert({ ...next, fileIndex: min.fileIndex });
      }
    }

    // 4. 将合并结果写入下一层的新SSTable
    const newSSTables: SSTable[] = [];
    const TARGET_FILE_SIZE = 64 * 1024 * 1024;  // 64MB per file
    let currentBatch: [K, V][] = [];
    let currentSize = 0;

    for (const entry of mergedEntries) {
      const entrySize = entry[0].length + JSON.stringify(entry[1]).length;

      if (currentSize + entrySize > TARGET_FILE_SIZE && currentBatch.length > 0) {
        const newSST = await this.writeSSTable(currentBatch, level + 1);
        newSSTables.push(newSST);
        currentBatch = [];
        currentSize = 0;
      }

      currentBatch.push(entry);
      currentSize += entrySize;
    }

    if (currentBatch.length > 0) {
      const newSST = await this.writeSSTable(currentBatch, level + 1);
      newSSTables.push(newSST);
    }

    // 5. 原子更新manifest（元数据）
    await this.atomicUpdate({
      deleteFiles: [...toCompact, ...overlapping],
      addFiles: newSSTables,
      fromLevel: level,
      toLevel: level + 1,
    });

    // 6. 删除旧文件
    for (const file of [...toCompact, ...overlapping]) {
      await this.deleteSSTable(file);
    }

    // 7. 检查下一层是否也需要compaction
    nextLevel.totalSize = nextLevel.sstables.reduce((sum, sst) => sum + sst.fileSize, 0);
    if (nextLevel.totalSize > nextLevel.maxSize) {
      await this.compact(level + 1);
    }
  }

  private selectFilesForCompaction(level: Level): SSTable[] {
    if (level.level === 0) {
      // L0: 所有文件都参与compaction
      return [...level.sstables];
    } else {
      // L1+: 选择得分最高的文件（基于大小和上次compaction时间）
      return level.sstables.slice(0, 1);  // 简化：选第一个
    }
  }

  private findOverlappingFiles(level: Level, files: SSTable[]): SSTable[] {
    const minKey = Math.min(...files.map(f => f.minKey));
    const maxKey = Math.max(...files.map(f => f.maxKey));

    return level.sstables.filter(sst => 
      !(sst.maxKey < minKey || sst.minKey > maxKey)
    );
  }

  private async atomicUpdate(update: any): Promise<void> {
    // 更新MANIFEST文件（简化）
    // 确保元数据更新的原子性
  }

  private async deleteSSTable(sst: SSTable): Promise<void> {
    // 删除物理文件
    // await fs.unlink(sst.fileId);
  }

  private createSSTableIterator(sst: SSTable): AsyncIterator<{ key: K; value: V }> {
    // 创建SSTable的迭代器（简化）
    return {
      async next() {
        return { key: "" as K, value: null as any as V };
      }
    };
  }
}

Compaction的写放大

Compaction虽然优化了读性能，但会带来额外的写放大：

// Leveled Compaction的写放大分析
function calculateLeveledWriteAmplification(numLevels: number, fanout: number): number {
  // 每个数据最终会写入多次：
  // 1次写入MemTable -> L0
  // L0 -> L1: 写入1次，读取fanout个L1文件，写入fanout个文件
  // L1 -> L2: 同上
  // ...
  // 总写放大 ≈ 1 + fanout * (numLevels - 1)

  return 1 + fanout * (numLevels - 1);
}

console.log(calculateLeveledWriteAmplification(7, 10));
// 写放大约 61x！
// 但这是顺序写，比B-Tree的随机写快得多

写入性能

# Python性能测试（伪代码）
import time
import random

def benchmark_writes(db, num_writes):
    keys = [f"key_{i}" for i in range(num_writes)]
    values = [f"value_{random.randint(0, 1000000)}" for _ in range(num_writes)]
    
    start = time.time()
    for k, v in zip(keys, values):
        db.put(k, v)
    end = time.time()
    
    return {
        "total_time": end - start,
        "ops_per_sec": num_writes / (end - start),
        "avg_latency_ms": (end - start) * 1000 / num_writes
    }

# 结果示例（1M随机写）：
# B-Tree (InnoDB):    50,000 ops/s,  20μs avg latency
# LSM-Tree (RocksDB): 200,000 ops/s, 5μs avg latency
# LSM-Tree 写入快 4倍！

读取性能

def benchmark_reads(db, num_reads):
    keys = [f"key_{random.randint(0, 1000000)}" for _ in range(num_reads)]
    
    start = time.time()
    hits = 0
    for k in keys:
        if db.get(k) is not None:
            hits += 1
    end = time.time()
    
    return {
        "total_time": end - start,
        "ops_per_sec": num_reads / (end - start),
        "hit_rate": hits / num_reads,
        "avg_latency_ms": (end - start) * 1000 / num_reads
    }

# 结果示例（100K随机读，冷缓存）：
# B-Tree (InnoDB):    80,000 ops/s,  12.5μs avg latency
# LSM-Tree (RocksDB): 30,000 ops/s,  33μs avg latency
# B-Tree 读取快 2.6倍！

范围查询性能

def benchmark_range_scans(db, num_scans, scan_size=100):
    start = time.time()
    for _ in range(num_scans):
        start_key = f"key_{random.randint(0, 1000000)}"
        results = db.range(start_key, scan_size)
    end = time.time()
    
    return {
        "total_time": end - start,
        "scans_per_sec": num_scans / (end - start),
        "avg_latency_ms": (end - start) * 1000 / num_scans
    }

# 结果示例（1K范围扫描，每次100条记录）：
# B-Tree (InnoDB):    5,000 scans/s,  200μs avg latency
# LSM-Tree (RocksDB): 3,000 scans/s,  333μs avg latency
# B-Tree 略优，因为数据在磁盘上连续

MySQL InnoDB：经典B+Tree

-- InnoDB使用B+Tree作为主索引（聚簇索引）
-- 数据直接存储在B+Tree的叶子节点

CREATE TABLE users (
  id BIGINT PRIMARY KEY,  -- B+Tree聚簇索引
  email VARCHAR(255) UNIQUE,  -- B+Tree二级索引
  name VARCHAR(100),
  created_at TIMESTAMP,
  INDEX idx_created (created_at)  -- B+Tree二级索引
) ENGINE=InnoDB;

-- 点查询：O(log n)
SELECT * FROM users WHERE id = 12345;
-- 通过主键B+Tree直接定位，3-4次磁盘I/O

-- 范围查询：B+Tree的强项
SELECT * FROM users 
WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'
ORDER BY created_at;
-- 通过idx_created索引顺序扫描，非常高效

InnoDB适用场景：

• OLTP事务处理（读写混合）
• 需要强一致性和ACID保证
• 范围查询频繁
• 数据更新频率中等

RocksDB：高性能LSM引擎

// RocksDB C++ API
#include <rocksdb/db.h>

rocksdb::DB* db;
rocksdb::Options options;

// 配置LSM参数
options.create_if_missing = true;
options.write_buffer_size = 64 << 20;  // 64MB MemTable
options.max_write_buffer_number = 3;   // 最多3个MemTable
options.level0_file_num_compaction_trigger = 4;  // L0有4个文件时触发compaction
options.max_bytes_for_level_base = 256 << 20;  // L1最大256MB
options.max_bytes_for_level_multiplier = 10;   // 每层放大10倍

// 打开数据库
rocksdb::Status status = rocksdb::DB::Open(options, "/path/to/db", &db);

// 批量写入（高吞吐）
rocksdb::WriteBatch batch;
for (int i = 0; i < 1000000; i++) {
  batch.Put("key_" + std::to_string(i), "value_" + std::to_string(i));
}
db->Write(rocksdb::WriteOptions(), &batch);
// 可达到 200K+ ops/s

RocksDB适用场景：

• 写密集型工作负载（日志、时序数据）
• 需要极高写入吞吐量
• 可以接受读放大的代价
• 闪存/SSD存储（顺序写充分利用SSD性能）

Cassandra/ScyllaDB：分布式LSM

-- Cassandra使用LSM存储引擎
CREATE TABLE events (
  user_id UUID,
  event_time TIMESTAMP,
  event_type TEXT,
  payload BLOB,
  PRIMARY KEY (user_id, event_time)
) WITH CLUSTERING ORDER BY (event_time DESC)
  AND compaction = {
    'class': 'LeveledCompactionStrategy',
    'sstable_size_in_mb': 160
  };

-- 高速写入
INSERT INTO events (user_id, event_time, event_type, payload)
VALUES (uuid(), toTimestamp(now()), 'click', 0x...);
-- 写入延迟 < 1ms，吞吐量可达百万级

-- 时间序列查询
SELECT * FROM events
WHERE user_id = ? 
  AND event_time > ?
  AND event_time < ?
ORDER BY event_time DESC;

Cassandra适用场景：

• 大规模时序数据（IoT、监控、日志）
• 需要线性扩展的写入能力
• 可用性优先于一致性（AP系统）
• 数据量TB到PB级

PostgreSQL：混合策略

-- PostgreSQL默认使用B-Tree索引
-- 但支持多种索引类型

CREATE TABLE documents (
  id SERIAL PRIMARY KEY,  -- B-Tree
  content TEXT,
  tags TEXT[],
  metadata JSONB,
  created_at TIMESTAMP
);

-- GIN索引（类似LSM的思想：追加优化）
CREATE INDEX idx_tags ON documents USING GIN(tags);
CREATE INDEX idx_metadata ON documents USING GIN(metadata);

-- GIN索引对写入进行批处理，类似LSM的MemTable
-- 查询时可能需要读取多个部分，有读放大

SELECT * FROM documents WHERE tags @> ARRAY['postgresql', 'database'];
-- GIN索引高效处理数组和JSON查询

B-Tree优化

// 1. 增加页面大小，减少树高度
const PAGE_SIZE = 16384;  // 16KB instead of 4KB

// 2. 使用前缀压缩
interface CompressedBTreeNode {
  commonPrefix: string;  // 公共前缀
  suffixes: string[];    // 各键的后缀
}

// "user_123", "user_456", "user_789"
// => { commonPrefix: "user_", suffixes: ["123", "456", "789"] }
// 节省空间，每个节点可以存更多键

// 3. 使用分形树（Fractal Tree）：TokuDB
// 在B-Tree节点中加入缓冲区，延迟刷盘，减少随机写

LSM-Tree优化

// 1. 分区Compaction（Partitioned Compaction）
// 将每层分成多个分区，并行compaction
interface PartitionedLevel {
  partitions: Partition[];
}

interface Partition {
  keyRange: [string, string];
  sstables: SSTable[];
}

// 2. Universal Compaction（适合小数据集）
// 不分层，所有SSTable同一层级，选择相似大小的文件合并

// 3. Tiered Compaction（Cassandra STCS）
// 将相似大小的SSTable分组，组内合并
// 写放大更低，但空间放大更高

// 4. 布隆过滤器优化
class OptimizedBloomFilter {
  // 使用分块布隆过滤器，支持部分加载
  private blocks: Uint8Array[];

  // 使用更优的哈希函数（MurmurHash3）
  private hash(key: string, seed: number): number {
    // MurmurHash3实现
    return 0;
  }
}

// 5. 缓存优化
interface LSMCache {
  blockCache: LRUCache<string, Block>;  // 热数据块缓存
  indexCache: LRUCache<string, IndexBlock>;  // 索引块缓存
  bloomCache: LRUCache<string, BloomFilter>;  // 布隆过滤器缓存
}

WiscKey：键值分离

// WiscKey的核心思想：只在LSM-Tree中存储键，值单独存储
interface WiscKeyLSM {
  lsm: LSMTree<string, ValuePointer>;  // LSM只存指针
  valueLog: AppendOnlyLog<string>;     // 值存在追加日志
}

interface ValuePointer {
  offset: number;
  size: number;
}

// 好处：
// 1. LSM-Tree更小，compaction更快
// 2. 大值不参与compaction，减少写放大
// 3. 范围查询只扫描键，按需加载值

Bε-Tree：延迟B-Tree

// Bε-Tree在B-Tree内部节点添加缓冲区
interface BEpsilonNode<K, V> {
  keys: K[];
  children?: BEpsilonNode<K, V>[];
  buffer?: BufferedOperation<K, V>[];  // 缓冲区！
}

interface BufferedOperation<K, V> {
  type: "INSERT" | "UPDATE" | "DELETE";
  key: K;
  value?: V;
}

// 写入先进缓冲区，满了再向下推送
// 结合了B-Tree的读性能和LSM的写性能

自适应引擎：RUM Conjecture

根据RUM猜想（Read-Update-Memory Overhead），存储系统无法同时优化三个维度：

• Read：读性能
• Update：写性能
• Memory：空间开销

// 自适应存储引擎：根据工作负载动态切换策略
class AdaptiveStorageEngine {
  private currentStrategy: "btree" | "lsm" | "hybrid";
  private metrics: WorkloadMetrics;

  async analyze(): Promise<void> {
    const readRatio = this.metrics.reads / (this.metrics.reads + this.metrics.writes);

    if (readRatio > 0.8) {
      // 读密集：使用B-Tree
      await this.switchToBTree();
    } else if (readRatio < 0.2) {
      // 写密集：使用LSM-Tree
      await this.switchToLSM();
    } else {
      // 混合负载：使用混合策略
      await this.switchToHybrid();
    }
  }

  private async switchToBTree(): Promise<void> {
    // 迁移数据到B-Tree结构
  }

  private async switchToLSM(): Promise<void> {
    // 迁移数据到LSM-Tree结构
  }

  private async switchToHybrid(): Promise<void> {
    // 热数据用B-Tree，冷数据用LSM
  }
}