B 树 (order=3):
         [10|20]
        /   |   \
    [5|7] [13|17] [25|30]

B+ 树 (order=3):
         [10|20]           ← 内部节点只有键
        /   |   \
  [5|7|→] [13|17|→] [25|30|→]  ← 叶子节点有数据 + 兄弟指针
       └──→ ──┘ └──→ ──┘

内部节点:
- 每个键: 8 字节 (BIGINT) + 6 字节 (子指针) = 14 字节
- 每页可容纳: 16384 / 14 ≈ 1170 个键
- 分支因子: ~1170

叶子节点:
- 每条记录: 100 字节 (数据) + 26 字节 (行头+事务ID+滚指针) = 126 字节
- 每页可容纳: 16384 / 126 ≈ 130 条记录
- 填充因子: ~70% → 实际 ~91 条

树的高度:
- 高度 1: 91 条记录
- 高度 2: 1170 × 91 = 106,470 条
- 高度 3: 1170 × 1170 × 91 = 124,518,300 条 (1.2亿)
- 高度 4: 1170^3 × 91 ≈ 1456 亿条

结论: 10亿条记录的表，B+ 树高度为 3-4 层
每次点查需要 3-4 次 I/O（缓冲池可缓存根节点和部分内部节点）

分裂前:
Page A (已满): [k1, k2, k3, ..., k_n]

分裂后:
Page A (前半): [k1, k2, ..., k_m]
Page B (后半): [k_m+1, ..., k_n]
父节点新增: [k_m+1] → 指向 Page B

如果父节点也满了 → 递归分裂 → 可能增加树的高度

写入路径:
Client → Write → WAL → MemTable (内存) → [满了] → SSTable (磁盘)

读取路径:
Client → Read → 先查 MemTable → 再查 Immutable MemTable → 
       → 依次查 Level 0, Level 1, ..., Level N 的 SSTable

MemTable 结构 (SkipList):
Level 3:  [1] ──────────────────────→ [50]
Level 2:  [1] ──→ [10] ────────────→ [50] ──→ [80]
Level 1:  [1] → [5] → [10] → [20] → [50] → [65] → [80]
Level 0:  [1] → [3] → [5] → [8] → [10] → [15] → [20] → ...

插入: 从最高层开始查找，逐层下降 → O(log n)
查找: 从最高层开始，逐层缩小范围 → O(log n)

SSTable 文件结构:
┌──────────────────────────────┐
│         Data Block 0         │  ← 有序的键值对
├──────────────────────────────┤
│         Data Block 1         │
├──────────────────────────────┤
│           ...                │
├──────────────────────────────┤
│         Data Block N         │
├──────────────────────────────┤
│        Index Block           │  ← 每个 Data Block 的最后一个键 + 偏移
├──────────────────────────────┤
│       Bloom Filter           │  ← 用于快速判断键是否存在
├──────────────────────────────┤
│       Meta Block             │  ← 元数据（统计信息等）
├──────────────────────────────┤
│    Footer (Magic Number)     │  ← 文件头信息
└──────────────────────────────┘

Data Block (压缩前):
┌────────────────────────────────┐
│ key_len | val_len | key | val  │  ← 键值对 1
├────────────────────────────────┤
│ key_len | val_len | key | val  │  ← 键值对 2
├────────────────────────────────┤
│           ...                  │
├────────────────────────────────┤
│        Restart Points          │  ← 用于二分查找的锚点
├────────────────────────────────┤
│   num_restarts | checksum     │
└────────────────────────────────┘

前缀压缩:
原始: [abc123, abc456, abc789]
压缩: [abc123, 3|456, 3|789]  ← 共享前缀 "abc"

Level 0:  [SST0] [SST1] [SST2]     ← 从 MemTable 刷写，键范围可重叠
Level 1:  [SST3] [SST4] [SST5] ... ← 键范围不重叠，每层最多 10× 上层大小
Level 2:  [SST...] ...              ← 更大的层
Level N:  ...

Compaction 过程:
1. 选择 Level L 的一个 SSTable
2. 找到 Level L+1 中键范围重叠的所有 SSTable
3. 多路归并这些 SSTable → 生成新的 Level L+1 SSTable
4. 删除旧的 SSTable

特点:
- 读放大小: 每个键最多存在于每层一个 SSTable 中
- 写放大大: 同一条数据可能经历多次 Compaction
- 空间放大小: 数据只存在于一个层级

Tier 0:  [SST0] [SST1] [SST2]     ← 键范围可重叠
Tier 1:  [SST3] [SST4] [SST5]     ← 键范围可重叠
Tier 2:  [SST6] [SST7] [SST8] ...

Compaction 过程:
1. 选择一个 Tier 中所有 SSTable
2. 多路归并 → 生成新的 Tier+1 SSTable
3. 删除旧 SSTable

特点:
- 读放大大: 同一个键可能存在于多个 SSTable 中
- 写放大小: 数据移动次数少
- 空间放大大: 可能存在多份过期数据

Bloom Filter 结构:
位数组: [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]  (16 bits)
哈希函数: h1, h2, h3

插入 "hello":
h1("hello") = 3  → [0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
h2("hello") = 7  → [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
h3("hello") = 12 → [0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0]

查询 "hello": h1=3(1), h2=7(1), h3=12(1) → 可能存在 ✓
查询 "world": h1=3(1), h2=5(0) → 一定不存在 ✗

没有 Bloom Filter 的读取:
查找 key="user:1001"
→ 查 Level 0 SSTable 0: 不在 (1次 I/O)
→ 查 Level 0 SSTable 1: 不在 (1次 I/O)
→ 查 Level 1 SSTable 3: 不在 (1次 I/O)
→ 查 Level 1 SSTable 4: 找到了! (1次 I/O)
总计: 4 次 I/O

有 Bloom Filter 的读取:
查找 key="user:1001"
→ Level 0 SSTable 0 Bloom Filter: 不存在 → 跳过
→ Level 0 SSTable 1 Bloom Filter: 不存在 → 跳过
→ Level 1 SSTable 3 Bloom Filter: 可能存在 → 查找 (1次 I/O)
→ Level 1 SSTable 4 Bloom Filter: 可能存在 → 查找 (1次 I/O)
总计: 2 次 I/O (节省 50%)

Bloom Filter 的误判率通常为 1%-2%，占用空间约 10-12 bits/key

选择指南:
- 读多写少（10:1 以上）→ B+ 树
- 写多读少（10:1 以上）→ LSM 树
- 读写均衡 → 取决于延迟敏感度
  - 延迟敏感 → B+ 树（延迟更稳定）
  - 吞吐优先 → LSM 树（写入吞吐更高）

class BPlusTreeNode:
    def __init__(self, leaf=True):
        self.leaf = leaf
        self.keys = []
        self.children = []
        self.next = None  # 叶子节点的兄弟指针
        self.values = []  # 叶子节点的值

class BPlusTree:
    def __init__(self, order=4):
        self.root = BPlusTreeNode()
        self.order = order

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node.leaf:
            if key in node.keys:
                idx = node.keys.index(key)
                return node.values[idx]
            return None
        else:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            return self._search(node.children[i], key)

    def insert(self, key, value):
        self._insert(self.root, key, value)
        if len(self.root.keys) > self.order - 1:
            new_root = BPlusTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split(new_root, 0)
            self.root = new_root

    def _insert(self, node, key, value):
        if node.leaf:
            i = 0
            while i < len(node.keys) and node.keys[i] < key:
                i += 1
            node.keys.insert(i, key)
            node.values.insert(i, value)
            if len(node.keys) >= self.order:
                self._split_leaf(node)
        else:
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            self._insert(node.children[i], key, value)

    def range_query(self, start_key, end_key):
        node = self._find_leaf(self.root, start_key)
        result = []
        while node:
            for k, v in zip(node.keys, node.values):
                if start_key <= k <= end_key:
                    result.append((k, v))
                if k > end_key:
                    return result
            node = node.next
        return result

# 使用示例
tree = BPlusTree(order=4)
for i in range(1, 21):
    tree.insert(i, f"value_{i}")

print("Search key=10:", tree.search(10))
print("Range [5,15]:", tree.range_query(5, 15))

import os
import json
from sortedcontainers import SortedDict

class SimpleLSMTree:
    def __init__(self, memtable_size=100, data_dir="/tmp/lsm"):
        self.memtable = SortedDict()
        self.memtable_size = memtable_size
        self.sstables = []  # 磁盘上的 SSTable 列表
        self.data_dir = data_dir
        os.makedirs(data_dir, exist_ok=True)

    def put(self, key, value):
        self.memtable[key] = value
        if len(self.memtable) >= self.memtable_size:
            self._flush_memtable()

    def get(self, key):
        # 1. 先查 MemTable
        if key in self.memtable:
            val = self.memtable[key]
            return None if val == "__DELETED__" else val

        # 2. 再查 SSTable（从新到旧）
        for sst in reversed(self.sstables):
            if key in sst:
                val = sst[key]
                return None if val == "__DELETED__" else val
        return None

    def delete(self, key):
        self.put(key, "__DELETED__")

    def _flush_memtable(self):
        if not self.memtable:
            return
        sst_path = os.path.join(self.data_dir, f"sst_{len(self.sstables)}.json")
        with open(sst_path, 'w') as f:
            json.dump(dict(self.memtable), f)
        self.sstables.append(dict(self.memtable))
        self.memtable = SortedDict()

    def compact(self):
        if len(self.sstables) < 2:
            return
        merged = SortedDict()
        for sst in self.sstables:
            merged.update(sst)
        # 删除标记为删除的键
        merged = {k: v for k, v in merged.items() if v != "__DELETED__"}
        self.sstables = [dict(merged)]

# 使用示例
lsm = SimpleLSMTree(memtable_size=5)
lsm.put("alice", 25)
lsm.put("bob", 30)
lsm.put("charlie", 35)
print("Get alice:", lsm.get("alice"))  # 25
lsm.delete("bob")
print("Get bob:", lsm.get("bob"))      # None