说实话，我很少见过把“数据结构”和“数据库”放在同一个项目标题里认真做拆解的。大多数情况下，这俩在开发者脑子里是两条平行线：写业务时关心SQL和表结构，刷题时才想起二叉树和哈希表。今天聊的这套练习项目代号是9-Decisions，里面把数据结构与数据库的关联及操作揉在一起做了九组对照实验，目的很直接：搞清楚索引为什么是B+树、哈希表在数据库里到底怎么用、一条慢SQL背后是哪种数据结构选型出了问题。这篇文章把其中最核心的几个决策点展开讲清楚，顺便给一份可以直接抄作业的最小存储引擎实现。
1. 先搞清楚一件事：数据结构不是数据库的附属品，而是底座
1.1 表、索引、日志，本质都是数据结构的实例
很多人写SQL写了一两年，脑子里依然没有数据结构的画面感。但数据库本身就是一堆数据结构拼起来的：表可以看成行对象的集合，主键索引是一棵B+树，普通索引是另一棵B+树但叶子里存的是主键值，事务日志是只追加的单向链表，连接池的队列是链表或环形数组，缓存则是哈希表加LRU链表。SQL只是操作这些数据结构的描述语言，优化器负责把你的SQL翻译成对具体数据结构的访问路径。
我在9-Decisions里做过一个很直观的对比实验：同样一万行记录，用线性数组挨个找，平均要比较五千次；用哈希表找，平均接近一次定位；用带索引的B+树找，按对数级别比较，也就十几次。这个差距反映到数据库里，就是全表扫描和走索引的天壤之别。所以理解数据库性能问题，本质上是在理解数据结构选型问题，这句话听起来有点像废话，但你真去排查一条慢SQL时，就会发现所有优化手段最后都落在“换一种数据结构访问方式”上。
1.2 一个键值数据库的最小形态，就是哈希表加日志
为了把“关联”这件事落到实处，我当时设计了一个思维模型：内存里放一个大哈希表，所有写操作先更新哈希表，同时把操作按顺序追加写入磁盘日志文件；启动时把日志逐条重放，哈希表就恢复了。写、读、恢复三条路径全部覆盖，而且只有几十行代码能实现。
这个模型看起来简陋，但它已经具备了一个键值存储的核心骨架：内存结构负责快速读写，磁盘日志负责持久化，恢复过程依赖日志的可重放性。市面上很多存储中间件虽然加了各种缓存、压缩、分片，但底层逻辑都逃不开这个框架。等后面落到实操时，你会发现这个模型的每一个细节都有对应的数据库概念。
2. 索引选型：为什么大家都选B+树，而不是二叉树
2.1 磁盘IO次数决定树的高度是生死线
先算一笔账：传统机械磁盘一次随机IO大约需要10ms，SSD虽然快很多，但也要0.1ms量级，而内存访问是几十纳秒。这中间的差距，决定了数据库索引必须尽量减少磁盘访问次数。
假设用一棵二叉树做索引，100万条数据需要约20层，查询一个键要从根节点一路往下走到叶子，20次随机IO。机械盘上就是200ms，这还没算数据在多个节点之间跳转的寻道时间。就算在SSD上，20次随机读也比一次顺序读慢得多。所以二叉树不是能力问题，是IO次数问题。
B+树则完全不同。非叶子节点只存键和指针，不存数据，所以每个节点能容纳的分支数量远超二叉树。拿InnoDB举例：默认页大小是16KB，如果索引项按16字节估算（键值加指针），一个非叶子页差不多能存1000个分支；叶子页假设每行记录约1KB，一个页能放16条数据。两层非叶子分支数是1000乘1000，等于100万个分支，再乘以每个叶子页的16条，约1600万条记录只需要3层。也就是说，走主键索引查一条数据，磁盘IO次数大约就是3次左右，这跟二叉树的20次根本不在一个量级上。
2.2 B+树、B树和哈希索引的取舍
很多人分不清B树和B+树的区别，简单说：B树的每个节点都存数据，B+树只有叶子节点存数据，非叶子节点只存索引项，并且叶子节点之间用链表串联。
这个差异带来三个直接结果：第一，B+树的非叶子节点能存更多分支，树更矮；第二，B+树做范围查询时，找到第一个叶子节点后沿着链表顺序往后读就行，而B树需要在中序遍历中不断回溯；第三，B+树的非叶子节点不存数据，整个索引结构更紧凑，缓存命中率更高。所以主流关系型数据库的聚簇索引都选了B+树。
哈希索引则是另一个极端：等值查询直接定位到桶，速度极快，但完全不适合范围查询，也不支持排序。Redis里的哈希表、MySQL Memory引擎的哈希索引，都只服务等值场景。
| 索引结构 | 等值查询 | 范围查询 | 排序支持 | 磁盘IO特征 | 典型场景 |
|---|---|---|---|---|---|
| B+树 | 快 | 快 | 天然有序 | 稳定，树高3~4层 | InnoDB主键/二级索引 |
| B树 | 较快 | 弱 | 弱 | 节点存数据，页利用率低 | 早期文件系统索引 |
| 哈希索引 | 极快 | 不支持 | 不支持 | 一次定位 | 缓存、等值查询密集场景 |
2.3 跳表、倒排索引、前缀树各回各家
除了B+树和哈希表，数据库领域还有几种必须认识的数据结构。Redis有序集合用的是跳表，它用多层链表实现二分查找，代码实现比红黑树简单，范围查询也顺手，所以成了有序集合的首选。Elasticsearch用的是倒排索引，本质是“词项到文档列表”的映射，搜索关键词时直接查词项字典，再拉出文档列表，跟关系型数据库的索引逻辑完全不是一回事，但依然是一个典型的数据结构应用题。前缀树则常见于IP路由和自动补全场景，把公共前缀压缩存储，查询效率跟字符串长度相关。
我还想单独提一下布隆过滤器。它不是一个完整的数据结构，而是一种概率型结构，用来快速判断一个键“一定不存在”还是“可能存在”。数据库和缓存中间件里大量用它拦截不存在的查询，避免无效IO。后面实操部分我会把它加进最小存储引擎里，你会直观感受到引入前后的差别。
2.4 LSM树：写密集场景的另一条路线
B+树虽然读性能好，但写路径要维护树的平衡，随机更新会带来大量随机IO。对海量写场景，LSM树换了一条思路：把随机写变成顺序写。写入先进内存中的有序结构（跳表或红黑树），达到阈值后整体落盘成不可变的有序文件，后台再对这些文件做归并合并。代价是读路径可能要查多个段，所以LSM树通常配合布隆过滤器和分层合并策略来控制读放大。
这套设计在RocksDB、HBase等存储引擎里很常见，适合物联网数据采集、消息队列存储这类写多读少的业务。理解了B+树和LSM树的差异，你就能理解为什么不同的数据库产品在硬件选型、写入吞吐、读延迟上差异那么大。
3. 数据库里最常见的“SQL慢”，其实都是数据结构问题
3.1 排序：数据量一上来，内存排不下怎么办
凡是ORDER BY、GROUP BY、DISTINCT，背后都可能涉及排序。数据能全部装进内存时，用快速排序即可；数据量超过内存可用空间时，数据库会走外部排序，而外部排序的经典算法就是归并排序：先把数据分块读入内存，每块排好序写回临时文件，再把这些有序分块逐步合并成一个有序结果集。
我之前在9-Decisions里做过一次参数测试，把sort_buffer_size从默认值调大之后，一个约两百万行的排序SQL执行时间明显下降，原因是减少了临时文件的生成轮数。但也不能一味调大，内存是全局资源，排序缓冲占多了，其他连接就会受影响。这就是典型的数据结构思维：先估算数据量能不能装进内存，再决定要不要落到外部归并。
3.2 去重、分组、连接：哈希和排序的博弈
GROUP BY的实现通常有两种路径：一种是基于排序去重，另一种是基于哈希去重。排序去重会利用已有索引顺序，避免额外排序；哈希去重在内存充足时更快，因为它只做一次哈希定位，不需要全局有序。MySQL 8.0里很多GROUP BY场景就默认走哈希聚合了。
连接操作的实现也类似。嵌套循环连接适合小表驱动大表，数据量小的时候最简单直接；哈希连接适合等值连接，先给内表建哈希表，再用外表逐行探测，内存足够时比嵌套循环快很多；排序合并连接适合非等值连接或数据已经有序的情况。写SQL时理解这些实现，你会自然明白为什么等值条件比复杂表达式更快，为什么连接要尽量用小表驱动大表。
3.3 建表时的数据结构思维
我建表时会先问几个问题：这个字段的查询模式是等值还是范围？读多还是写多？数据量级增长是线性还是突发？等值查询多，优先考虑哈希索引或普通B+树索引；范围查询多，B+树几乎唯一选择；时间序列数据考虑按时间分区，分区本质上是把一棵大B+树拆成多棵小B+树；标签过滤场景，则可能要引入倒排索引或宽表设计。数据结构选型前移到建模阶段，比事后加索引省钱得多。
4. 亲手实现一个廉价版存储引擎，把关联焊死
4.1 内存结构：哈希表承接写操作
实践出真知。我建议你跟我一起写一个十来行的键值存储核心，语言用Python，重点看思路。代码很短，但关联了前面所有概念。
import os import json import threading class DemoKV: def __init__(self, path): self.path = path self.mem = {} self.lock = threading.Lock() self._load() def _load(self): if not os.path.exists(self.path): return with open(self.path, "r", encoding="utf-8") as f: for line in f: if not line.strip(): continue record = json.loads(line) self.mem[record["k"]] = record["v"] def set(self, k, v): with self.lock: self.mem[k] = v with open(self.path, "a", encoding="utf-8") as f: f.write(json.dumps({"k": k, "v": v}) + "\n") def get(self, k): return self.mem.get(k)这段代码的逻辑很直白：set操作更新内存哈希表，同时把操作追加到文件末行。get操作直接查内存哈希表。注意文件写入用了追加模式，这可不是随便选的，顺序写比随机写快得多，这也是后面理解LSM树的入口。
4.2 持久化结构：只能追加的日志
为什么用追加日志而不是直接修改文件里的某个位置？一方面，追加写永远只发生在文件末尾，磁头和闪存不需要频繁寻道，写性能稳定；另一方面，追加日志天然记录全量操作历史，即使中途崩溃，恢复时重放日志就能回到最近的一致状态。存储引擎领域把这个文件叫作Write-Ahead Log，不管多复杂的数据库，这条原则都适用。
日志里的每条记录是JSON格式，简单但够用。每次set操作都写一条完整记录，包括键和值。这里有一个细节：如果同一个键被反复写入，日志里会有多条重复记录，恢复时按顺序重放，最后的写入会覆盖前面的值。这是日志重放的幂等基础。
4.3 全量日志重放的问题，以及分段合并
上面的代码有个严重缺陷：日志越来越大，启动时全量重放会越来越慢。这就引出了存储引擎设计的下一层：把日志分段，内存达到阈值就把当前哈希表变成一个不可变的快照段，后续新写入进新段，启动时只需要加载最新的完整段，再重放少量增量日志。后台再对多个段做归并压缩，清理那些被覆盖的旧键。这个思路已经是LSM树的雏形。
class DemoSegment: def __init__(self, segment_id, data): self.segment_id = segment_id self.data = data class DemoLSM: def __init__(self, base_dir): self.base_dir = base_dir self.mem = {} self.mem_size = 0 self.segments = [] self.max_mem_size = 64 * 1024 * 1024 def set(self, k, v): self.mem[k] = v self.mem_size += len(k) + len(v) if self.mem_size >= self.max_mem_size: self._flush() def _flush(self): seg_id = len(self.segments) path = f"{self.base_dir}/{seg_id}.json" with open(path, "w", encoding="utf-8") as f: json.dump(self.mem, f, ensure_ascii=False) self.segments.append(DemoSegment(seg_id, dict(self.mem))) self.mem = {} self.mem_size = 0 def get(self, k): if k in self.mem: return self.mem[k] for seg in reversed(self.segments): if k in seg.data: return seg.data[k] return None这个版本已经能正确处理写入和查询，但每次flush产生的段会越来越多，查询要逆序检查每段，读路径变成O(段数)，所以后台合并任务会把相邻小段合并成大段，并把过期键清理掉。合并过程本质上就是归并排序，跟前面说的外部排序是同一个方法论。
4.4 花一行代码优化“不存在的查询”
再往深走一步：查询一个不存在的键时，上面的DemoLSM必须检查内存然后逐段找，段一多就是灾难。解决办法是给每个段配一个布隆过滤器，查询段之前先问过滤器：这个键可能在这个段里吗？如果回答不可能，直接跳过这个段。原理很简单：布隆过滤器用多个哈希函数把键映射到位数组，判断不存在时一定准确，判断存在时可能误判。用在存储引擎里可以把大量无意义的磁盘读取挡在门外。
这里的核心收获是：存储引擎的性能优化从来不是单点魔法，而是把内存、磁盘、索引结构、概率结构组合起来，找到读写路径上的平衡点。
5. 排查慢SQL时的数据结构视角（含速查表）
5.1 索引失效，本质上是有序结构的失效
开发中最常遇到的慢查询问题，就是明明建了索引，SQL却不用。用9-Decisions的视角看，大部分情况不是索引坏了，而是查询表达式让B+树无法按有序结构走。
典型例子是在索引列上套函数，比如WHERE LEFT(name, 3) = 'abc'，B+树只能按完整键值排序，函数计算后顺序信息完全丢失。另一个常见问题是隐式转换，字段是varchar类型，条件却传了数字，数据库为了比较可能把字段转成数字，索引同样失效。还有一个隐蔽场景：联合索引里写了范围查询，比如WHERE a = 1 AND b > 100 AND c = 5，B+树在b上走范围后，c字段的有序性已经被破坏，无法继续利用。
这些都指向同一个本质：索引之所以快，是因为底层结构维护了有序性或哈希映射，一旦查询条件破坏了这种性质，结构就退化为普通扫描。
5.2 从执行计划反推访问的数据结构
EXPLAIN输出的type列是排查入口。从system、const、eq_ref、ref、range、index到ALL，基本反映了优化器决定用哪种方式访问数据。ref说明走了非唯一索引的等值匹配，range说明走了范围扫描，index说明索引全扫描但覆盖了查询列，ALL就是全表扫描。再用key_len看索引实际用到的字节数，就能判断联合索引到底使用了几个字段。
我排查慢SQL时有一个固定流程：先看type是不是ALL或index，再看key是否为NULL，然后看rows估算值，最后结合字段类型和查询条件判断是否发生隐式转换或函数破坏。整套动作下来，基本都能定位到“数据结构访问路径”这一层。
5.3 慢SQL排查速查表
| 现象 | 可能原因 | 数据结构视角 | 处理建议 |
|---|---|---|---|
| 查询不走索引，type=ALL | 索引列使用函数或隐式转换 | 有序结构被破坏，B+树无法二分 | 改写条件，避免在索引列上做计算 |
| 联合索引只用到一部分 | 范围查询后跟其他索引列 | B+树范围边界后不再有序 | 调整字段顺序，或拆成多个索引 |
| 排序慢且出现filesort | 排序字段无法利用索引顺序 | B+树叶子链表本可提供顺序读 | 让ORDER BY字段走索引，或调大排序缓冲 |
| 大表COUNT(*)慢 | 引擎层没有维护条目计数 | 聚簇索引遍历成本高 | 用计数表或近似值替代 |
| 分页越深越慢 | LIMIT 100000, 20会扫描前面所有行 | 叶子链表顺序读但无效记录太多 | 改游标分页，用上次最大主键过滤 |
| 写入越来越慢 | 索引过多导致每次写放大 | 每棵B+树都要维护结构 | 精简索引，或考虑LSM类存储 |
6. 实操复盘：我在9-Decisions里最值得留存的三个决策
6.1 决策一：能用顺序访问就不要随机访问
做那组测试时，我把约500MB数据分别放在机械盘和SSD上跑全表扫描和随机点查。机械盘上顺序读和随机读的差距是数量级的，SSD上依然有很大差距，只是绝对值小了一些。这个体验直接影响了我后面的设计习惯：能设计成顺序写入就不要频繁更新随机位置，能批量读就不要逐条点查。存储引擎的追加日志、LSM树的顺序写，本质上都在服从这个原则。
6.2 决策二：数据结构选型要考虑读写比例
读多写少，B+树加足够大的内存缓存最省心；写多读少，LSM树那套思路更合适；实时统计分析场景，列式存储能跳过无关字段；文档检索场景，倒排索引绕不开。我见过不少团队把业务表设计成单一大宽表，以为省了关联查询，结果因为字段太多、索引太杂，写入和查询都在变慢。先想清楚读写配比，再选索引和表结构，这个顺序不能反。
6.3 决策三：先想清楚数据的生命周期
数据也有热温冷之分。热数据放在内存结构里，温数据走索引，冷数据归档到独立存储。归档表面上是省空间，实际是把大B+树拆掉、缩小了每次查询的扫描范围。我在模拟项目里清理了一部分历史数据后，一个大表的查询性能提升非常明显，而这只是把索引层次降低了一层。数据生命周期管理不是DBA专属话题，作为开发者，建表时就应该想好数据从产生到归档的全路径。
最后分享一个我个人的习惯：分析任何数据库问题时，先把时间开销换算成磁盘IO次数。一条SQL慢，慢在几次随机IO、几次全表扫描、几次排序落盘，答案通常就很清楚了。这个习惯是我做9-Decisions数据结构的最大收获，也希望能帮你在自己的项目里少走一些弯路。
