一、为什么MemTable是存储引擎的核心枢纽
1.1 MemTable的真实作用
我们平时用的数据库，比如LevelDB，要把数据存在硬盘上，可硬盘的“脾气”很慢，每次读或写都要等好久，要是把用户的每一条写请求都直接存到硬盘，那系统肯定卡得不行。所以工程师想了个办法：搞一块内存区域，叫MemTable，用来临时存刚收到的数据，等攒够一定数量，再一起转成有序的硬盘文件（也就是SSTable）。
MemTable的要求特别高：第一，写要快，每秒得扛得住几万甚至几十万条请求；第二，读也要快，用户查数据的时候，不能等太久；第三，数据还要有序，因为转成硬盘文件的时候，有序的话合并起来更省时间，不然乱七八遭的，合并的时候要扫好几遍，浪费磁盘IO。
二、跳表 vs 红黑树：大白话讲清两者是什么
很多人选MemTable的底层结构时，会纠结跳表和红黑树，其实两者都是“有序的、可以快速增删查的数据结构”，但实现起来差得特别多。
2.1 红黑树：带颜色的平衡二叉树
你可以把红黑树想象成一棵“左右平衡的二叉树”，每个节点还带个颜色（红色或黑色），它的规则很简单：根节点是黑色，相邻节点不能都是红色，所有从根到叶子的路径上，黑色节点的数量要一样。这么设计的目的是，不管怎么插入删除，树都不会长得歪歪扭扭，找数据的时候最多走几十步，比普通链表快多了。
举个简化的例子，用Python写的红黑树核心结构（不含完整平衡逻辑，只看样子）：
# 技术栈：Python 3.8
# 红黑树简化实现，仅展示核心结构，不包含完整平衡逻辑
class RBNode:
RED = True
BLACK = False
def __init__(self, key):
self.key = key # 数据的键，比如用户的ID
self.color = RBNode.RED # 新节点默认红色，这是红黑树的基础规则
self.left = None # 左子节点
self.right = None # 右子节点
self.parent = None # 父节点
class SimpleRBTree:
def __init__(self):
self.root = None # 树根节点
# 简化版插入，没有做平衡，只是把节点放到正确位置
def insert(self, key):
new_node = RBNode(key)
if not self.root:
self.root = new_node
self.root.color = RBNode.BLACK # 根必须是黑色
return
current = self.root
parent = None
# 找插入位置
while current:
parent = current
if key < current.key:
current = current.left
elif key > current.key:
current = current.right
else:
# 重复键，忽略，简化处理
return
# 把新节点挂到父节点上
new_node.parent = parent
if key < parent.key:
parent.left = new_node
else:
parent.right = new_node
# 查找数据
def search(self, key):
current = self.root
while current:
if key < current.key:
current = current.left
elif key > current.key:
current = current.right
else:
return True # 找到
return False # 没找到
# 测试代码
rbt = SimpleRBTree()
for k in [1,3,5,2,4]:
rbt.insert(k)
print("查找key=3是否存在：", rbt.search(3)) # 输出True
2.2 跳表：带“电梯”的有序链表
跳表就聪明多了，它是个“加了多层索引的有序链表”。普通的有序链表，找数据要从头走到尾，比如找第100个元素，要走100步。但跳表搞了几层“电梯”：最高层的电梯跨100个节点，中间层跨10个，最底层就是普通链表。找数据的时候，先坐最高层电梯，快到目标了再换低层，这样最多只需要走几十步，和红黑树的速度差不多，但实现起来简单太多。
用Python写的简化跳表，核心增删查逻辑如下：
# 技术栈：Python 3.8
# 跳表简化实现，展示核心增删查逻辑，和LevelDB的核心结构一致
import random
class SkipNode:
def __init__(self, key, level):
self.key = key # 数据的键
self.forward = [None]*(level+1) # 每层的指针，比如level=2有3个指针（0、1、2层）
class SimpleSkipList:
def __init__(self, max_level=12, p=0.25):
self.max_level = max_level # 最高层级，LevelDB用的是12层
self.p = p # 节点晋升高层的概率，LevelDB用0.25
self.level = 0 # 当前跳表的最高层级，初始是0
self.head = SkipNode(-1, self.max_level) # 头节点，所有指针都指向空
# 随机生成新节点的层级，符合概率规则
def random_level(self):
level = 0
while random.random() < self.p and level < self.max_level:
level +=1
return level
# 插入操作，从高层往下找，每层更新前驱节点
def insert(self, key):
update = [None]*(self.max_level+1) # 每层需要更新的前驱节点
current = self.head
# 从最高层走到0层，找到插入位置
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
update[i] = current # 记录每层的前驱
current = current.forward[0]
# 如果key已存在，简化处理不做更新
if not current or current.key != key:
new_level = self.random_level()
# 新层级比当前高，要更新高层的前驱为头节点
if new_level > self.level:
for i in range(self.level+1, new_level+1):
update[i] = self.head
self.level = new_level
# 创建新节点，每层插入到对应位置
new_node = SkipNode(key, new_level)
for i in range(new_level+1):
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
# 查找操作，和插入的搜索逻辑一致
def search(self, key):
current = self.head
for i in range(self.level, -1, -1):
while current.forward[i] and current.forward[i].key < key:
current = current.forward[i]
current = current.forward[0]
return current and current.key == key
# 测试代码
sl = SimpleSkipList()
for k in [1,3,5,2,4]:
sl.insert(k)
print("查找key=3是否存在：", sl.search(3)) # 输出True
三、两者在MemTable场景下的真实差异
现在回到MemTable的场景，我们从三个维度对比：应用场景、技术优缺点、注意事项。
3.1 应用场景的适配
红黑树适合什么？适合需要严格平衡、对最坏情况要求高的场景，比如内存数据库的复杂数据结构，但它对操作的“稳定性”要求不高，比如偶尔有几次慢操作也没关系。但MemTable不一样，它需要每秒处理大量请求，每一次写都要快，不能突然卡一下。跳表的操作是固定的，不管什么数据，插入删除最多改几个指针，不会出现突然要旋转几十次的情况，更稳定。
3.2 核心操作的性能差异
我们来算个简单的账：假设要插入10万条数据，红黑树的插入，每一次都要检查颜色、旋转，平均要做几十次操作；而跳表的插入，平均只需要做十几次操作，常数更小，速度更快。而且，跳表的遍历特别简单，只要从0层的头节点往后走就行，而红黑树的遍历要按中序，虽然也是O(logn)，但代码逻辑复杂，遍历的时候也容易出问题。
3.3 注意事项
红黑树的坑特别多：比如根节点必须是黑色，插入后如果出现红色相邻节点，要马上变色或旋转，要是漏了一步，树就会不平衡，后续的查找速度会变慢，调试的时候很难找到问题，比如某个插入后树歪了，你得一行行查代码，花几个小时。而跳表的坑只有两个：一是层级的设置，LevelDB用的max_level=12，p=0.25，这个参数是算出来的，足够应付100万条数据；二是随机生成层级的概率，不能随便改，不然空间或性能会受影响，这些参数只要调对了，就很少出问题。
四、LevelDB最终选跳表的真实原因
很多人以为LevelDB选跳表是因为性能更好，其实不是，是因为它“适合工程实现”，是务实的选型：
4.1 实现复杂度低，代码量少
LevelDB是用C++写的，要快还要开发成本低。红黑树的完整实现，包括插入、删除、平衡、旋转，要写几百行代码，还要处理各种边界情况，比如删除节点的时候，颜色调整、指针移动，很容易写错。而跳表的实现，只有几百行，核心逻辑就是插入、删除、层级随机，代码量少，出bug的概率也低，后期维护起来特别轻松。
4.2 操作性能稳定，无突发高峰
跳表的每一次操作，不管是插入、删除还是查找，都是固定的步骤，最多改几个指针，不会出现“突然要旋转十几圈”的情况，所以延迟特别稳定，对于MemTable来说，延迟稳定比绝对的性能高更重要，因为MemTable是写请求的第一道关卡，要是延迟忽高忽低，用户体验会特别差。
4.3 适配MemTable的有序性需求
MemTable转成SSTable的时候，需要有序的结构，跳表天然有序，遍历的时候直接按顺序来，不用额外处理排序，省了很多事。红黑树也有序，但遍历的逻辑复杂，而且转成硬盘文件的时候，要是结构乱了，还要重新排序，浪费时间。
五、总结
MemTable的选型，从来不是选“最先进的数据结构”，而是选“最适合场景的结构”。跳表和红黑树都能满足MemTable的性能要求，但跳表实现简单、稳定，适合LevelDB这种追求工程效率的存储引擎。这就是为什么LevelDB最终选了跳表，而不是红黑树的真实原因。
评论
围绕“跳表与红黑树在存储引擎MemTable选型中的真实差异，为什么LevelDB最终选择了前者”参与讨论