> LSM Tree（Log-Structured Merge Tree）是现代高写入吞吐存储引擎的核心数据结构，通过将随机写转换为顺序写，大幅提升写入性能。RocksDB、LevelDB、TiKV、Cassandra、HBase 均以 LSM Tree 为底层引擎。 相关文章：Bloom Filter · B+ Tr…
2026-06-02
> Bloom Filter 是一种空间极度高效的概率型数据结构，用 O(1) 时间和远小于实际数据的空间回答"某个元素是否在集合中"。无假阴性（在集合中的元素一定能查到），有假阳性（查到不代表一定存在）。RocksDB、Cassandra、HBase、Nginx 均大量使用。 相关文章：LSM Tree · SSTa…
2026-06-02
> B+ Tree 是关系型数据库索引的主流数据结构，MySQL InnoDB、PostgreSQL、etcd（boltdb）均以 B+ Tree 为核心。本文深入 B+ Tree 的节点结构、插入分裂、删除合并等算法细节，并与 B-Tree、LSM Tree 做深度对比。 相关文章：LSM Tree · SSTabl…
2026-06-02
> SSTable（Sorted String Table）是 LSM Tree 的磁盘存储格式：一个不可变的、按 key 有序排列的键值对文件。理解 SSTable 是理解 LSM Tree 读写路径、Compaction 机制的基础。LevelDB、RocksDB、Cassandra、HBase 均使用 SSTab…
2026-06-02
> Copy-on-Write（写时复制）是一种延迟复制的优化策略：多个读者共享同一份数据，只有在需要修改时才创建副本。它是实现无锁读、原子更新、低代价快照的核心机制，广泛用于操作系统、数据库、文件系统和编程语言运行时。 相关文章：LSM Tree · Roaring Bitmap --- 目录 | 章节 | 说明 |…
2026-06-02
> Roaring Bitmap 是一种高效的压缩整数集合数据结构，根据数据密度自动选择最优的存储容器，在稀疏和密集场景下都能保持极低的内存占用与高效的集合运算。ClickHouse、Druid、Lucene/ES、Apache Spark 等大数据系统广泛使用。 相关文章：Bloom Filter · Copy-on…
2026-06-02
> WAL（Write-Ahead Log）通过"先写日志再改数据"保证崩溃后数据可恢复，是 InnoDB、PostgreSQL、etcd、RocksDB 等几乎所有持久化存储系统的核心机制。 相关文章：Bitcask · Redo 与 Undo Log --- 目录 | 章节 | 说明 | |------|-----…
2026-06-04
> Bitcask 通过追加写日志 + 全量内存索引（KeyDir）实现读 O(1)、写 O(1) 的高性能 KV 存储，是 Riak 默认存储引擎，也被 Erlang 系系统广泛采用。 相关文章：WAL（Write-Ahead Log） · Redo 与 Undo Log --- 目录 | 章节 | 说明 | |--…
2026-06-04
> Redo Log 记录"做了什么"（物理变更）用于崩溃后重做已提交事务，Undo Log 记录"如何撤销"（逻辑旧值）用于回滚未提交事务与 MVCC 历史版本，两者共同实现 InnoDB、PostgreSQL 等数据库的 ACID 保障。 相关文章：WAL（Write-Ahead Log） · Bitcask --…
2026-06-04
> Varint 与 ZigZag 编码解决了固定长度整数编码浪费空间的问题，广泛应用于 Protobuf、Thrift、Avro 等序列化框架，小数值可节省 50%~75% 存储空间。 相关文章：Delta 编码 · LZ4 与 Snappy 与 Zstd !varint zigzag 目录 | 章节 | 说明 | …
2026-06-04