数据密集型应用系统设计Read Note-第三章-数据存储与检索

《数据密集型应用系统设计》第三章“数据存储与检索”核心内容总结如下：

数据结构与索引基础

KV存储的简单实现将键值对逐行存储在文件中，写效率高但读效率低。索引作为派生数据结构可加速查询，但会降低写入速度。
哈希索引的优化设计
Bitcask引擎：通过内存中的哈希表（HashMap）记录键到磁盘文件偏移量的映射，支持追加式文件的高效写入。
段管理策略：将日志分解为多个小段，每段维护独立哈希表，并通过后台线程压缩合并段（丢弃重复键、保留最新值）。
关键问题处理：
文件格式：采用二进制格式替代CSV以减少空间占用。
删除操作：追加删除标记，合并时清理已删除键。
崩溃恢复：定期将内存哈希表快照存储到磁盘，重启时直接加载。
并发控制：单写线程与多读线程的隔离设计。
追加日志优势：顺序写提升磁盘性能、段不可变性简化并发与恢复、合并减少文件碎片。
哈希索引局限：内存依赖性强（不适合海量键）、区间查询效率低、哈希冲突风险。

SSTables与LSM-Tree

SSTable（排序字符串表）
核心特性：键值对按Key排序存储，每个键在段文件中唯一出现。
优势：
合并高效：通过多段键比较实现快速归并。
区间查询优化：仅需保存部分键索引即可定位范围数据。
分块压缩：减少存储空间占用。
实现方式：内存中采用红黑树或AVL树维护有序键值，写入时追加日志用于崩溃恢复。
应用场景：LevelDB、RocksDB、Cassandra等数据库。
LSM-Tree（日志结构合并树）
原理：基于多层级排序文件的合并与压缩，优化写入性能。
优化技术：
布隆过滤器：快速判断键不存在，减少磁盘访问。
分级存储：按文件大小或时间分层管理，平衡查询与合并效率。
类比应用：Lucene全文搜索引擎采用类似SSTable的结构存储单词到文档ID的映射。

B-Tree与关系型数据库

B-Tree的核心设计
结构：多路平衡树，每个节点包含多个键值对和子节点指针。
关键机制：
WAL（预写日志）：确保崩溃时数据可恢复。
锁控制：通过锁机制实现并发读写隔离。
应用场景：传统关系型数据库（如MySQL、PostgreSQL）的默认索引结构。

图：B-Tree的层级结构与节点布局其他索引结构

事务处理与分析处理分离

OLTP与OLAP的差异
OLTP（在线事务处理）：高并发、低延迟的读写操作，适合行存储引擎。
OLAP（在线分析处理）：大规模数据扫描与聚合，适合列存储引擎。
数据仓库的ETL流程
提取（Extract）：从OLTP系统导出原始数据。
转换（Transform）：清洗、转换数据格式（如星型模式）。
加载（Load）：将结构化数据导入分析型数据库。

图：ETL流程与数据仓库的分层设计列存储与物化聚合

列存储的核心优势
存储效率：按列压缩数据（如位图编码），减少磁盘I/O。
查询性能：仅加载需要的列，适合大规模聚合操作。
写入机制：通过LSM-tree管理内存缓冲区，合并后写入磁盘列文件（如Vertica实现）。
物化视图与数据立方体
物化视图：预计算查询结果并持久化，加速特定查询但影响写入性能。
数据立方体：多维聚合数据的预计算结构，优化复杂分析查询但缺乏灵活性。

图：星型模式中的事实表（fact_sales）与维度表关系

图：二维数据立方体的聚合维度示例总结

本章围绕数据存储与检索的核心问题，系统阐述了从简单KV存储到复杂索引结构（如LSM-Tree、B-Tree）的设计原理，并对比了事务处理与分析处理的架构差异。列存储与物化聚合技术的引入，进一步优化了大规模数据分析场景的性能与成本平衡。

热门标签