外部存储结构：外排序、倒排索引与 LSM Tree
学了这么多数据结构之后，如果一直停留在“数据都能放进内存里”的想象里，视角其实还是不够完整。真实系统里，很多真正有挑战的问题，都发生在数据规模远超内存的时候：
- 日志量特别大；
- 索引体积很大；
- 搜索和存储都要依赖磁盘；
- 一次访问的成本不再是 CPU 比较，而是磁盘 I/O。
这时，数据结构设计的重点就会发生明显变化。外部存储结构之所以重要，就在于它提醒我们：
当内存不再是唯一主战场，结构设计必须围绕块访问、顺序 I/O、批量写入和磁盘友好性重新考虑。
这一篇不准备把外存系统细节讲得过重，而是先从数据结构视角，把三类非常有代表性的外部存储相关结构思路串起来：外排序、倒排索引和 LSM Tree。它们虽然用途不同，但都在回答同一个问题：大规模数据怎样在外存上组织得更高效。
一、为什么外部存储问题和内存数据结构不一样
在内存结构里，我们习惯了：
- 随机访问代价低；
- 指针跳转相对便宜；
- 结构细粒度调整成本可控。
但在外存里，真正昂贵的通常是：
- 一次磁盘寻址；
- 一次随机 I/O；
- 把很多小写操作零散地刷到磁盘。
所以外存结构通常更重视：
- 顺序读写；
- 块级访问；
- 批量合并；
- 降低随机 I/O 次数。
这就是为什么 B+ 树、LSM Tree 这种结构会和内存中的红黑树风格明显不同。
二、什么是外排序
外排序可以理解成：
当数据量大到内存放不下时，借助磁盘分批读写完成排序的过程。
如果数据完全在内存里，排序算法我们已经见过很多；但当数据太大时，就不能直接一次性加载全部元素。这时通常会采用两阶段思路：
- 先把数据分块读入内存，各自排序后写回磁盘；
- 再对这些有序块做多路归并。
所以外排序的核心不是“发明新排序顺序”，而是：
让排序过程适配“数据放不下、I/O 很贵”的现实。
三、外排序为什么通常依赖多路归并
因为多路归并特别适合顺序 I/O。
如果你已经有多个磁盘上的有序段，那么：
- 顺序读取每段的当前头部；
- 选出最小元素写入输出；
- 再继续推进对应段；
就能把多个大文件逐步归并成更大的有序结果。
而且归并过程可以很好地利用缓冲区和顺序读取，避免过多随机磁盘访问。
四、什么是倒排索引
倒排索引是搜索系统里最典型的数据结构之一。它的核心思想可以理解成：
不是记录“文档包含哪些词”，而是记录“某个词出现在哪些文档中”。
例如：
- 词
data出现在文档 1、3、8； - 词
structure出现在文档 2、3、5；
那么搜索某个词时，就可以直接定位到对应文档集合。
这之所以叫“倒排”，是因为它把原本“文档 -> 词”的方向反了过来，变成了“词 -> 文档列表”。
五、为什么倒排索引特别适合搜索
因为搜索引擎最常做的事情不是“遍历所有文档看谁包含关键词”，而是：
- 给定关键词；
- 迅速拿到候选文档集合；
- 再做交集、排序、打分。
如果没有倒排索引，每次搜索都得扫描全部文本，这在大规模系统里根本无法接受。
所以倒排索引本质上是：
为“按词找文档”这个操作量身定制的索引结构。
六、倒排索引和 Trie / 哈希表有什么关系
倒排索引本身通常由两部分组成：
- 词典；
- 倒排列表。
而词典层可以用：
- 哈希表；
- B+ 树；
- Trie；
等结构去维护。也就是说，倒排索引不是脱离已有结构的新世界，而是把很多基础结构组合到搜索场景里的一种组织方式。
七、什么是 LSM Tree
LSM Tree，全称通常是 Log-Structured Merge Tree。它是现代存储系统和数据库里非常经典的一种结构，尤其适合写多读多、磁盘友好的场景。
它最核心的思想可以概括成：
先把写入集中落到内存和顺序磁盘文件中，再通过后台合并，把多个有序段逐步整理起来。
也就是说，它不像 B+ 树那样总在原位置做更新，而是更偏向：
- 先积累；
- 再批量刷盘；
- 再定期合并。
八、LSM Tree 为什么适合高写入场景
因为它尽量避免随机写磁盘。
典型思路通常是：
- 新写入先进入内存表；
- 内存表满了，再顺序刷成一个磁盘上的有序文件；
- 磁盘上逐渐形成多个有序层；
- 后台再做合并压缩。
这样做的好处是：
- 把很多离散小写操作转成顺序大写；
- 显著提升写入吞吐；
- 很符合现代 SSD / 磁盘系统的 I/O 特性。
九、LSM Tree 的代价是什么
它不是没有代价。典型代价包括：
- 查询时可能要查多个层级 / 多个文件；
- 删除通常是逻辑删除，再靠后续 compaction 真正清理；
- 后台合并本身会带来额外 I/O 和写放大。
所以 LSM Tree 的本质是一种非常典型的工程权衡：
- 牺牲一部分读路径简单性；
- 换来非常强的写入友好性。
十、外排序、倒排索引和 LSM Tree 的共同点是什么
表面上它们分别属于排序、搜索、数据库存储，但从数据结构视角看，它们其实有共同逻辑：
- 都要面对“数据量太大，无法只靠内存”；
- 都要围绕磁盘 I/O 重新设计组织方式；
- 都更重视顺序访问、批量处理和索引结构；
- 都不是简单把内存结构搬到磁盘，而是重新适应外存特性。
这就是外部存储结构最值得建立的认识。
十一、学习外部存储结构时最容易踩的坑
1. 只从内存复杂度看问题
在外存场景里，I/O 次数往往比单纯比较次数更重要。
2. 把 B+ 树、LSM Tree、倒排索引看成互相替代
它们常常服务的目标并不相同。
3. 不了解顺序 I/O 和随机 I/O 差异
这是理解外存结构设计的关键背景。
4. 误以为外部结构只是“数据更大而已”
其实设计哲学都变了。
总结
外部存储结构的重要性，不只是因为它们对应更大的数据量，而是因为它们迫使你真正从“内存友好”切换到“磁盘友好”的视角。真正值得先建立起来的，是这些核心认识：
- 外存数据结构关注的核心通常是块访问、顺序 I/O 和批量处理；
- 外排序用分块排序加多路归并解决“大到内存放不下”的排序问题；
- 倒排索引把“词 -> 文档列表”作为核心组织方向，是搜索系统的基础结构；
- LSM Tree 通过先写内存、后顺序刷盘、再后台合并的方式优化写入；
- 这些结构都说明：数据结构设计必须服从存储介质的物理特性；
- 真正学会这一篇，不是记住几个名词，而是意识到“当数据上磁盘后，结构设计的优先级已经完全变了”。
把这一篇理解透之后，后面再去学并发结构和工程实践时，你会更容易把数据结构和真实系统联系起来，而不只是停留在内存模型的抽象世界里。
参考资源：