Module 2: 数据模型与存储引擎

📖 深度参考手册 — 本模块属于理论参考，非主线必读。 主线学习路径见 README.md。 当你在项目实战中遇到相关问题时，回来查阅。

来源：DDIA Ch2 (Data Models), Ch3 (Storage and Retrieval), Ch4 (Encoding)

---

2.1 关系模型 vs 文档模型 vs 图模型

定义：这是三种根本不同的数据组织方式。关系模型用表格（行和列）+ 外键表达数据间的关系，适合结构化数据和复杂查询（SQL）。文档模型用嵌套的JSON/BSON文档存储数据，适合”自包含”的数据单元，读取时一次性加载整个文档。图模型用节点（实体）和边（关系）组成网络结构，适合关系本身就是核心数据的场景。

为什么重要：选错数据模型是系统设计中代价最高的错误之一——通常在项目上线后才暴露，而此时迁移成本已经非常巨大。数据模型决定了你能写出什么样的查询、性能天花板在哪里、以及未来扩展的方向。面试中选择数据模型时如果能说清楚”为什么选这个而不是那个”，会大大加分。

案例：

Hotel Reservation 用关系模型：酒店预订系统的核心实体有酒店、房型、库存、订单、用户。它们之间有严格的关系：一个酒店有多种房型，每种房型每天有固定的库存，一个订单关联一个用户和一个房型。关键在于——预订操作需要事务保证（检查库存→扣减库存→创建订单必须是原子操作）。关系数据库的ACID事务天然支持这个需求。如果用文档模型，跨文档事务会非常复杂。

Hotels 1——N RoomTypes 1——N Inventory (每天)
Users 1——N Reservations N——1 RoomTypes

News Feed 用图模型：社交网络的核心是”关注关系”——用户A关注用户B，用户B关注用户C。要生成用户A的Feed，需要找到A关注的所有人，再找到这些人发布的内容。如果A关注了500人，这就是一个”从A出发，遍历500条关注边，收集终点节点的帖子”的图查询。关系数据库也能做（JOIN），但当关系链条变长（如”好友的好友推荐”）时，多层JOIN性能会急剧下降，而图数据库天然擅长多跳遍历。

先想一想 🤔 为什么大多数实际的社交网络（Twitter、Facebook）并没有用图数据库，而是用关系数据库+缓存来实现Feed？

点击查看解析

几个原因：1）图数据库在2010年代初还不够成熟，而这些公司在那之前就建立了技术栈；2）虽然"关注关系"适合图模型，但Feed系统的大部分操作（存储帖子、查询帖子、排序）其实是关系/键值操作，图查询只是其中一环；3）大规模图数据库的分片（partitioning）仍然是难题——关注关系很难自然分割；4）实际上这些公司通过预计算（fan-out on write）避免了实时图遍历——当用户发帖时直接把帖子推送到所有粉丝的Feed缓存中，读取时直接读缓存，根本不需要图查询。所以选型不只看"理论最优"，还要看实际工程可行性。

---

2.2 Schema-on-write vs Schema-on-read

定义：Schema-on-write（写时模式）要求数据在写入时必须符合预先定义的结构（如SQL的CREATE TABLE），不符合就报错拒绝。Schema-on-read（读时模式）不强制写入格式，数据以原始形式存储，在读取时由应用程序解释其结构。前者类似编译时类型检查（Java/Go），后者类似运行时类型检查（Python/JavaScript）。

为什么重要：这个选择影响系统的灵活性和可靠性之间的平衡。Schema-on-write保证数据质量但限制灵活性；Schema-on-read允许快速迭代但可能在运行时才发现数据问题。在系统设计面试中，能说清这个取舍说明你理解数据工程的核心矛盾。

案例：以 Search Engine 为例。搜索引擎需要爬取和索引整个互联网的数据——网页、PDF、图片、视频、结构化数据（如商品信息）、半结构化数据（如JSON-LD）。这些数据来源极其多样，格式千差万别：

• 新闻网站有标题、正文、发布时间
• 电商网站有商品名、价格、评分
• 学术论文有作者、摘要、引用
• 社交媒体有用户名、帖子内容、标签

如果用schema-on-write，你需要为每种数据源预定义schema——这不现实，因为互联网上的数据类型在不断增长。Schema-on-read让搜索引擎先把所有数据存下来（比如存为原始HTML+提取的文本+元数据JSON），然后在建索引和查询时，针对不同类型的数据用不同的解析器来解释。想加一个新的数据类型？不需要改存储层，只需要加一个新的读取解析器。

先想一想 🤔 既然schema-on-read这么灵活，为什么银行系统和酒店预订系统仍然坚持用schema-on-write？

点击查看解析

因为在这些场景中，数据正确性比灵活性重要得多。银行不能允许一笔转账记录缺少"金额"字段，酒店不能允许一条预订记录没有"入住日期"。Schema-on-write在写入时就拦截错误数据，而schema-on-read把验证推迟到读取时——如果半年后才发现某些预订记录格式有问题，可能已经造成了财务损失。此外，关系数据库的schema-on-write还支持外键约束和唯一约束，确保数据之间的引用关系完整。这种"严格保证"是金融和预订类系统的刚需。

---

2.3 哈希索引

定义：哈希索引是最简单的索引结构——在内存中维护一个哈希表，key是查询字段的值，value是该记录在磁盘上的字节偏移量。查询时先在内存哈希表中找到偏移量，然后一次磁盘seek直接读取数据。Bitcask（Riak的默认存储引擎）就是这种设计：所有key必须能放进内存，value存在磁盘上。

为什么重要：哈希索引是理解所有索引结构的起点。它展示了索引的本质——用额外的内存空间换取更快的查询速度。同时它也暴露了索引设计的核心权衡：哈希索引的精确查找极快（O(1)），但完全不支持范围查询（无法查”所有以A开头的key”），因为哈希表没有排序。

案例：URL Shortener 的 shortCode → originalURL 映射本质上就是哈希索引。思考一下核心读取路径：

1. 用户访问 https://tinyurl.com/abc123
2. 系统需要根据 abc123（shortCode）查到 https://example.com/very/long/path（originalURL）
3. 这是一个纯粹的精确键值查找——不需要范围查询、不需要排序、不需要模糊匹配

这和Bitcask的设计完美匹配：

• 所有shortCode（key）放在内存中——假设每个shortCode 7字符+8字节指针 = 15字节，10亿条 = 15GB内存，现代服务器轻松装下
• originalURL（value）存在磁盘上——一次磁盘seek就能读到
• 读取延迟：内存查找（~100ns）+ 一次磁盘读取（SSD ~100μs）≈ 100μs

先想一想 🤔 如果URL Shortener需要支持”查看某个用户创建的所有短链接”这个功能，纯哈希索引还够用吗？

点击查看解析

不够。"某个用户的所有短链接"是一个范围查询/过滤查询——需要按user_id查找所有匹配的记录。哈希索引只能做精确的key查找，无法扫描出"所有user_id=xxx的记录"。解决方案有两个：1）建一个额外的反向索引 `user_id → [shortCode列表]`，这本身也可以是一个哈希索引；2）使用B-Tree等支持范围查询的索引结构，在user_id字段上建索引。实际系统中通常会有多种索引共存，每种服务于不同的查询模式。

---

2.4 LSM-Tree与SSTable

定义：LSM-Tree（Log-Structured Merge-Tree）是一种为写入优化的存储结构。工作原理分三步：1）写入先进入内存中的有序结构（memtable，通常是红黑树或跳表）；2）当memtable达到阈值（如几MB），将其整体刷写为磁盘上的SSTable（Sorted String Table）——一个按key排序的不可变文件；3）后台持续将多个SSTable合并（compaction），消除重复和已删除的key。LevelDB、RocksDB、Cassandra、HBase都基于此结构。

为什么重要：LSM-Tree将随机写入转化为顺序写入——这是存储引擎设计中最重要的优化之一。磁盘（尤其是HDD）的顺序写入速度可以是随机写入的100倍以上。即使是SSD，顺序写入也有2-3倍的优势（减少写放大，延长寿命）。当系统的写入负载远大于读取负载时，LSM-Tree是首选。

案例：以 Gaming Leaderboard 为例。游戏排行榜的分数更新非常频繁：

• 假设一款全球在线游戏有1000万活跃玩家
• 每场游戏结束后更新分数，平均每个玩家每天玩10场
• 写QPS = 1000万 × 10 / 86400 ≈ 1157 QPS
• 高峰期（晚间）可能达到 5000+ QPS 的分数写入

每次分数更新在LSM-Tree中的流程：

1. PUT player:12345 → {score: 8500, updated_at: ...} 写入memtable（微秒级，纯内存操作）
2. memtable满了后刷成SSTable文件，按player_id排序
3. 后台compaction将多个SSTable合并，同一个player_id只保留最新分数

LSM-Tree在这里的优势：

• 写入极快（不需要像B-Tree那样找到页、分裂页）
• 分数的频繁更新不会导致磁盘随机写入
• compaction过程自然淘汰旧分数，起到数据清理作用

先想一想 🤔 LSM-Tree的读取为什么比写入慢？在Gaming Leaderboard中这个问题严重吗？

点击查看解析

读取慢是因为数据可能分布在memtable和多层SSTable中——最坏情况下需要查找memtable + 每一层的SSTable，直到找到key。优化手段包括：1）Bloom Filter——快速判断某个key是否可能在某个SSTable中，避免无效磁盘读取；2）compaction减少层数。对Gaming Leaderboard来说，这个问题不太严重，因为排行榜查询（Top N）通常是在Redis的Sorted Set中完成的（参考1.2节），LSM-Tree作为持久化存储，主要处理写入和历史查询。即使读取稍慢，也只是后台从存储加载到Redis缓存时的开销，不影响用户体验。

---

2.5 B-Tree索引

定义：B-Tree是几乎所有关系数据库的默认索引结构。它将数据组织为一棵平衡树：每个节点是一个固定大小的”页”（通常4KB），内部节点存储key和指向子节点的指针（用于导航），叶子节点存储key和实际数据（或数据的指针）。查找时从根节点开始，通过比较key值选择分支，一层层向下直到叶子节点。树的深度通常是3-4层（每层一次磁盘I/O），所以查找任何key最多需要3-4次磁盘读取。

为什么重要：B-Tree提供了稳定可预测的读取性能——无论数据量多大，查找时间都是O(log N)，且由于树很”扁”（每个节点扇出可达几百），实际磁盘I/O次数极少。它还天然支持范围查询（叶子节点按key排序并用链表相连），这是哈希索引无法做到的。理解B-Tree帮助你理解为什么关系数据库在OLTP场景中如此强大。

案例：以 Hotel Reservation 按日期范围查库存为例。用户搜索”3月15日到3月18日，杭州西湖附近的酒店”时，系统需要：

SELECT h.name, rt.type, inv.available_rooms, inv.price
FROM inventory inv
JOIN room_types rt ON inv.room_type_id = rt.id
JOIN hotels h ON rt.hotel_id = h.id
WHERE h.city = '杭州'
  AND inv.date BETWEEN '2026-03-15' AND '2026-03-18'
  AND inv.available_rooms > 0
ORDER BY inv.price ASC;

这个查询中，B-Tree索引发挥关键作用：

• 在 inventory(date) 上的B-Tree索引：快速定位3月15日到18日的库存记录，不需要扫描全表。叶子节点按日期排序，找到起始日期后顺序读取直到结束日期——这就是范围查询的优势。
• 复合索引 inventory(hotel_id, date) 更强：先定位到某个酒店，再在该酒店内按日期范围查找，两层过滤都利用B-Tree的有序性。

如果这里用哈希索引，只能做 date = '2026-03-15' 的精确查找，无法直接做 BETWEEN 范围扫描——需要逐天查询再合并，效率差很多。

先想一想 🤔 B-Tree的一个节点（页）通常是4KB，为什么不做成更大的比如1MB？更大的节点不是能存更多key，减少树的深度吗？

点击查看解析

理论上更大的节点确实能减少深度，但实际上有几个问题：1）每次修改一个key就要重写整个节点——如果节点是1MB，哪怕只改一个字节也要写1MB，写放大严重；2）操作系统和磁盘的最小I/O单位通常是4KB（一个"页"），读一个4KB节点只需一次I/O，读1MB节点需要256次I/O（或一次大的顺序I/O），如果只需要其中一个key，其他255个4KB全浪费了；3）内存中缓存页也以4KB为单位，节点越大，Buffer Pool中能缓存的节点越少，缓存命中率下降。4KB是操作系统、磁盘硬件、数据库三者之间的平衡点。

---

2.6 LSM-Tree vs B-Tree对比

定义：LSM-Tree和B-Tree是两种截然不同的存储引擎设计哲学。LSM-Tree通过将随机写入转化为批量顺序写入来优化写入性能，代价是读取时可能需要查找多层文件。B-Tree通过维护一棵始终有序的树结构来优化读取性能，代价是每次写入都需要原地更新（可能触发页分裂）。

为什么重要：在系统设计面试中，不同的系统有不同的读写比例，选对存储引擎直接影响性能天花板。这不仅是一个技术选型题，更考验你对工作负载（workload）的理解——你必须先分析系统是读密集还是写密集，才能做出合理选择。

特性	LSM-Tree	B-Tree
写入性能	优秀（顺序写入）	一般（随机写入+页分裂）
读取性能	较慢（需查多层）	稳定快速（3-4次I/O）
写放大	compaction造成	页分裂+WAL造成
空间利用率	高（compaction消除碎片）	一般（页可能半满）
范围查询	SSTable有序，尚可	叶子节点链表，优秀
并发控制	简单（不可变文件）	复杂（锁/锁协议）

案例对比：

Web Crawler（写密集 → LSM-Tree）：爬虫系统的核心工作是不断抓取网页并存储。假设目标是爬取100亿个网页：

• 持续写入URL和页面内容——写QPS极高
• 同一个URL可能被多次爬取（更新内容）——大量覆盖写入
• 批量读取用于后续处理（如建索引），对单条读取延迟不敏感
• LSM-Tree的顺序写入和compaction天然处理覆盖更新

Proximity Service（读密集 → B-Tree）：附近的人/商家服务：

• 数据（商家位置）相对稳定，写入很少（商家开业/倒闭）
• 用户不断查询”我附近的餐厅”——读QPS极高
• 需要范围查询（经纬度范围内的所有记录）
• 需要稳定可预测的延迟（用户在等结果）
• B-Tree的稳定读取性能和范围查询能力正好匹配

先想一想 🤔 如果一个系统读写各占50%，应该选LSM-Tree还是B-Tree？

点击查看解析

没有标准答案，需要进一步分析具体场景。考虑以下因素：1）读取对延迟是否敏感？如果是用户直接感知的请求（如搜索），B-Tree的稳定延迟更重要；如果是后台批处理，LSM-Tree也行。2）写入模式——是大量小写入还是少量大写入？大量小的随机写入LSM-Tree优势明显。3）是否需要事务？传统关系数据库（B-Tree）的事务支持更成熟。4）存储空间是否紧张？LSM-Tree的空间利用率更高。实际上很多现代数据库（如CockroachDB）底层用RocksDB（LSM-Tree）但上层提供SQL接口，说明二者的边界正在模糊化。最稳妥的做法是跑benchmark，用实际数据说话。

---

2.7 倒排索引

定义：倒排索引（Inverted Index）是一种从”内容”到”文档”的反向映射结构。正向索引是”文档→包含哪些词”，倒排索引是”词→出现在哪些文档中”。具体来说，倒排索引由两部分组成：词典（Term Dictionary）——所有不重复的词，按字母排序；倒排列表（Posting List）——每个词对应的文档ID列表，通常还包含词频、位置等附加信息。

为什么重要：几乎所有全文搜索系统的核心都是倒排索引——Elasticsearch/Lucene、Solr、Google搜索引擎概不例外。不理解倒排索引就无法理解搜索系统是如何工作的。在面试中设计任何涉及搜索的系统，倒排索引都是必须提到的数据结构。

案例：以 Search Engine 为例。假设我们有三个网页：

Doc1: "如何设计分布式系统"
Doc2: "分布式存储引擎的设计与实现"
Doc3: "系统设计面试指南"

分词后建立倒排索引：

词          → 倒排列表
"如何"       → [Doc1]
"设计"       → [Doc1, Doc2, Doc3]
"分布式"     → [Doc1, Doc2]
"系统"       → [Doc1, Doc3]
"存储"       → [Doc2]
"引擎"       → [Doc2]
"实现"       → [Doc2]
"面试"       → [Doc3]
"指南"       → [Doc3]

当用户搜索”分布式设计”时：

1. 在词典中查找”分布式” → [Doc1, Doc2]
2. 在词典中查找”设计” → [Doc1, Doc2, Doc3]
3. 求交集 → [Doc1, Doc2]（同时包含两个词的文档）
4. 按相关度排序（TF-IDF或BM25）返回结果

倒排索引的性能关键在于：词典查找用B-Tree或哈希索引（O(log N)或O(1)），倒排列表的交集/并集运算可以利用有序性做高效的归并操作。Google处理千亿级网页的搜索，核心依赖的就是这个看似简单的数据结构——只是规模大了之后需要分布式、压缩、缓存等工程优化。

先想一想 🤔 倒排索引擅长精确词匹配，但如何处理拼写错误（如用户搜”分部式”而不是”分布式”）？

点击查看解析

搜索引擎用几种技术处理模糊匹配：1）编辑距离（Levenshtein Distance）——计算"分部式"和词典中每个词的编辑距离，找到距离最小的词"分布式"作为纠正建议（"你是不是想搜..."）。为了提高效率，用BK-tree或SymSpell算法预计算。2）n-gram索引——把每个词拆成n个字符的片段（如"分布式"→"分布"、"布式"），拼错的词仍然能部分匹配。3）语音近似（Soundex/Metaphone）——适用于英文。4）用户行为学习——记录"搜分部式的用户最终点了分布式的结果"，下次直接纠正。实际搜索引擎通常组合使用以上多种技术。

---

2.8 列式存储

定义：列式存储（Columnar Storage）将同一列的所有值连续存放在磁盘上，而不是像行式存储那样将同一行的所有列值放在一起。例如有100万行的表，行式存储是”第1行所有列、第2行所有列…”，列式存储是”第1列的100万个值、第2列的100万个值…”。代表系统包括Apache Parquet（文件格式）、ClickHouse、Amazon Redshift。

为什么重要：分析查询（OLAP）通常只访问表中的少数几列——比如”统计所有用户的平均观看时长”只需要 watch_duration 一列，但行式存储会把每行的所有50个列都从磁盘读出来，浪费了98%的I/O。列式存储只读取需要的列，I/O效率提升数十倍。此外，同一列的数据类型相同、值域相近，压缩率极高（通常5-10倍）。

案例：以 YouTube 观看行为分析为例。YouTube需要分析用户的观看行为来优化推荐算法和广告投放。假设有一张观看记录表：

watch_events 表（数十亿行）：
| user_id | video_id | watch_duration | device | country | timestamp | quality | ... 共30列 |

典型分析查询：“过去7天，各国家用户的平均观看时长是多少？”

SELECT country, AVG(watch_duration)
FROM watch_events
WHERE timestamp > '2026-03-23'
GROUP BY country;

这个查询只需要3列：country、watch_duration、timestamp。

行式存储的处理方式：

• 扫描每一行，读取全部30列，只用其中3列
• 假设每行200字节，10亿行 = 200GB需要从磁盘读取
• 实际有用的数据只有约20GB（3列），浪费了90%的I/O

列式存储的处理方式：

• 只读取3列的数据文件
• country列：每个值约10字节，用字典编码后可能只要2字节，10亿 × 2B = 2GB
• watch_duration列：每个值4字节，10亿 × 4B = 4GB
• timestamp列：每个值8字节，但差值编码后约4字节，10亿 × 4B = 4GB
• 总I/O约10GB——是行式存储的1/20

先想一想 🤔 既然列式存储这么高效，为什么YouTube的核心业务（播放视频、发评论）不也用列式存储？

点击查看解析

因为列式存储的优势只在读取少数列的场景，而核心业务是写入和按行读取。当用户发一条评论时，需要写入一整行（user_id + video_id + content + timestamp + ...），列式存储需要分别追加到多个列文件中，写入开销比行式存储大得多。当用户查看某条视频的评论时，需要读取完整的行（显示用户名、评论内容、时间等所有字段），列式存储需要从多个列文件中分别取值再"拼装"回一行，效率反而比行式低。所以：OLTP（事务处理）用行式存储，OLAP（分析处理）用列式存储。实际上YouTube同时使用两种——MySQL/Bigtable处理实时业务，BigQuery（列式）处理分析查询。

---

2.9 数据编码与演化

定义：数据编码（序列化）是将内存中的数据结构转换为可以存储到磁盘或通过网络传输的字节序列的过程。常见格式包括JSON（人类可读，自描述）、Protocol Buffers/Protobuf（Google开发，二进制紧凑格式，需要schema文件）、Avro（Apache开发，紧凑二进制，schema和数据分离）。Schema演化指在不中断服务的情况下修改数据格式——向前兼容（新代码能读旧数据）和向后兼容（旧代码能读新数据）。

为什么重要：在大型分布式系统中，不同的服务、不同的服务器可能运行着不同版本的代码（滚动升级）。如果消息格式的改变导致旧版本代码无法解析新格式的数据，或者新版本代码无法理解旧格式的数据，系统就会崩溃。数据编码和演化策略确保系统在升级过程中保持正常运行。

案例：以 Chat System 为例。聊天消息的格式在产品生命周期中会不断演化：

v1（初始版本）：

message ChatMessage {
  string msg_id = 1;
  string sender_id = 2;
  string content = 3;
  int64 timestamp = 4;
}

v2（增加消息类型，如图片/语音）：

message ChatMessage {
  string msg_id = 1;
  string sender_id = 2;
  string content = 3;
  int64 timestamp = 4;
  MessageType type = 5;        // 新增字段
  string media_url = 6;        // 新增字段
}

v3（增加回复和表情反应）：

message ChatMessage {
  string msg_id = 1;
  string sender_id = 2;
  string content = 3;
  int64 timestamp = 4;
  MessageType type = 5;
  string media_url = 6;
  string reply_to_msg_id = 7;            // 新增
  repeated Reaction reactions = 8;        // 新增
}

Protobuf通过字段编号（而非字段名）来识别字段，天然支持演化：

• 向前兼容：运行v3代码的服务器收到v1格式的消息——新字段（type、media_url等）没有值，Protobuf自动赋默认值（空字符串/0），不会报错。
• 向后兼容：运行v1代码的旧客户端收到v3格式的消息——遇到不认识的字段编号（5、6、7、8）直接跳过，只读取字段1-4，不会崩溃。

这在聊天系统中至关重要——你不能强制所有用户同时更新App。可能有些用户还在用v1的App，但他们需要和使用v3 App的用户正常通信。

如果用JSON呢？JSON没有schema约束，增加新字段不会有解析错误，但也没有类型安全，而且JSON体积比Protobuf大3-10倍——在每天处理数十亿条消息的聊天系统中，这意味着巨大的带宽和存储成本差异。

先想一想 🤔 如果Chat System的v4版本需要把 content 字段从string改为一个复杂结构（支持富文本），怎么做才能保持兼容性？

点击查看解析

绝对不能直接修改字段3（content）的类型——这会同时破坏向前和向后兼容性。正确做法是：保留字段3（content）作为纯文本内容，新增字段9（rich_content）作为富文本结构。新版本的发送端同时填写两个字段——content放纯文本版本（兜底），rich_content放富文本版本。新客户端优先读rich_content，如果没有则降级读content。旧客户端只读content，完全不受影响。这就是"只增加新字段，永远不修改或删除已有字段"的演化原则。在Protobuf中，被废弃的字段编号甚至应该用 `reserved` 关键字锁定，防止未来误用。

---

练习

练习1：给”数据层”加新维度——这些数据适合什么存储引擎？为什么？

回顾11个系统案例的数据层，为每个系统的核心数据选择最合适的存储引擎，并说明理由。

使用以下分析框架：

系统	核心数据	读写比	查询模式	推荐存储引擎	理由
?	?	?	?	?	?

提示：考虑这些维度——

• 读密集 vs 写密集
• 精确查找 vs 范围查询 vs 全文搜索
• 是否需要事务
• 数据量级
• 延迟要求

点击查看参考答案

系统	核心数据	读写比	查询模式	推荐存储引擎	理由
URL Shortener	shortCode→URL映射	100:1	精确键值查找	内存哈希（Redis）+ 持久化	极高读QPS，纯键值查找，完美匹配哈希索引
Web Crawler	网页内容+URL队列	1:10	批量写入，少量查找	LSM-Tree（RocksDB）	写密集，大量覆盖更新，不需要实时读取
News Feed	帖子+社交关系	10:1	时间线范围查询+图遍历	B-Tree（关系DB）+ Redis缓存	需要按时间范围查询，关系数据需要JOIN
Chat System	消息记录	1:1	按会话时间范围查询	LSM-Tree（Cassandra）	大量写入，按时间顺序追加，按会话分区
Search Engine	网页索引	100:1	全文搜索	倒排索引（Lucene）	全文搜索是核心需求，倒排索引是唯一合理选择
YouTube	视频元数据+观看记录	10:1（元数据）1:5（观看记录）	精确查找+分析聚合	B-Tree（元数据）+ 列式存储（分析）	元数据需事务一致性，分析需高效列扫描
Google Drive	文件元数据+版本历史	5:1	按目录层级查询	B-Tree（关系DB）	树状目录结构适合B-Tree，需要事务（文件共享权限）
Proximity Service	位置POI数据	100:1	地理空间范围查询	B-Tree + 空间索引（R-Tree/GeoHash）	数据稳定读密集，需要二维范围查询
Google Maps	地图瓦片+路径数据	1000:1	精确瓦片查找+图最短路径	键值存储（瓦片）+ 图引擎（路径）	瓦片是静态数据精确查找；路径规划是图遍历
Hotel Reservation	库存+订单	5:1	日期范围查询+事务写入	B-Tree（PostgreSQL/MySQL）	强事务需求（防超卖），日期范围查询
Gaming Leaderboard	玩家分数	1:5	Top-N查询+频繁更新	Redis Sorted Set + LSM-Tree持久化	实时排名需内存速度，持久化用LSM处理写入

---

练习2：URL Shortener和Search Engine的数据在存储需求上有什么本质区别？

从以下角度对比分析：

1. 数据结构的复杂度
2. 查询模式
3. 数据的增长方式
4. 对一致性的要求
5. 索引结构的选择

点击查看参考答案

维度	URL Shortener	Search Engine
数据结构	极简——一个KV对（shortCode→URL），每条记录100字节左右	极复杂——每个文档有标题、正文、链接、元数据；还需要维护倒排索引、PageRank图等辅助数据结构
查询模式	单一——只有精确的键值查找（给定shortCode返回URL）	多样——全文搜索、模糊匹配、多条件过滤、相关度排序、拼写纠正、自动补全
数据增长	线性增长——每天新增N个短链接，旧的不变	指数级复杂度增长——新网页不仅新增文档，还改变了所有相关词的倒排列表，需要重新计算PageRank
一致性要求	高——短链接创建后必须立刻可用（用户点击需要立刻跳转）	低——网页被爬取后可以几分钟甚至几小时后才出现在搜索结果中（最终一致性）
索引结构	哈希索引——O(1)精确查找，不需要排序、不需要范围查询	倒排索引+B-Tree——倒排索引支持全文搜索，B-Tree索引支持元数据过滤和排序
存储规模	中等——10亿URL约100GB，单机可存	巨大——互联网数万亿网页，索引就要PB级，必须分布式存储
读写路径	读写路径都极简——写：生成shortCode→存入KV；读：查KV→返回URL	读写完全不对称——写（爬取+建索引）是重量级离线流水线；读（搜索）是轻量级在线查询

本质区别：URL Shortener的数据是”扁平”的——每条记录独立存在，互不关联，查询模式单一。Search Engine的数据是”立体”的——文档之间通过链接关联，词和文档之间通过倒排索引关联，查询需要在这个多维结构上做复杂运算。这决定了前者可以用最简单的存储方案（Redis/Memcached），而后者需要专门的搜索引擎（Elasticsearch/自研）。