跳表更合适——它平均o(log n)插入/查找，无锁实现简单，遍历天然有序且缓存友好，而红黑树标准库实现不支持高效迭代合并，std::unordered_map无序导致范围查询开销爆炸。
内存组件该用什么数据结构？跳表还是红黑树？
LSM树的内存组件（MemTable）必须支持有序插入、范围查询和快速迭代，同时写入性能要高。跳表（SkipList）比 std::map（红黑树）更合适——它平均 O(log n) 插入/查找，无锁实现简单，且遍历天然有序、缓存友好。
别用 std::unordered_map：它无序，做范围查询得先拷贝再排序，开销爆炸；也别手写红黑树——标准库没暴露节点指针，无法高效迭代合并到 SSTable。
- 直接采用 LevelDB/rocksdb 的跳表实现思路：固定层数（通常 12 层），随机化提升概率为 0.5
- 每个节点只存
key和value，不存序列号（seqnum）——那是 WAL 和 flush 时才加的元信息 - 用
std::atomic<bool></bool>控制是否只读（flush 触发后设为 true），避免加锁阻塞写入
如何避免 flush 时阻塞写入？双缓冲 MemTable
单个 MemTable 在 flush 到磁盘期间，新写入必须排队，吞吐掉一半以上。解决方案是维护两个活跃 MemTable：一个正在写（active），一个正在 flush（immutable）。当 active 写满（比如 64MB），立刻原子切换，新请求打到新分配的 active，旧的 immutable 交由后台线程异步 dump。
关键点不是“双缓冲”这个概念，而是切换时机和内存管理：
- 切换必须用
std::atomic_store+std::atomic_load，不能用互斥锁——否则写路径出现锁竞争 - immutable MemTable flush 完成后，不能立即
delete，要等所有读请求（可能还在遍历它）结束；用引用计数或 epoch-based reclamation（如std::shared_ptr）更稳妥 - 不要复用已分配内存：每次 new 一个新跳表，避免残留状态和并发访问冲突
Key 比较器怎么写才不影响压缩和查询正确性？
MemTable 的比较逻辑必须和后续 SSTable 的 key 比较器完全一致，否则 merge 过程会乱序，导致查不到数据或重复返回。C++ 中最容易踩坑的是字符串 key 的字节序和 null 字节处理。
例如，用 std::string 作 key 时，若业务 key 可能含 \0（如 protobuf 序列化结果），直接用默认 operator 会截断——因为 <code>std::string::c_str() 是 C 风格字符串，strcmp 遇 \0 就停。
- 定义自定义比较器，用
memcmp或std::lexicographical_compare比较 raw bytes - 把比较器类型作为模板参数传给跳表类，确保编译期绑定，避免虚函数调用开销
- 如果支持用户自定义 comparator（比如按时间戳倒序），务必在 flush 前序列化 comparator ID 到 SSTable header，否则 recovery 时无法重建正确顺序
内存占用怎么压？别让指针吃掉一半空间
跳表每层都要存指针，64 位系统下，一个 12 层跳表节点光指针就占 96 字节。如果 value 很小（比如 8 字节整数），节点本身比有效数据还大三倍。
优化方向很实际：降层数、紧凑存储、延迟分配：
- 把最大层数从 12 降到 8——实测 100 万条数据下，查找性能差异＜5%，但内存节省 33%
- 用
std::vector<:atomic>></:atomic>替代固定长度指针数组，按需增长；或者把指针数组放在节点末尾（flexible array member 风格），用malloc一次性分配 - value 不直接存进节点：改存
std::string_view或 offset+length，实际数据堆外管理（如 arena allocator），减少拷贝和碎片
真正难的不是写出来，是让 MemTable 在高吞吐写入下不抖动——这取决于指针局部性、allocator 选择和 flush 线程调度策略，而这些没法靠一个“优化技巧”解决。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
