MySQL的innodb是直接使用B-tree进行表组织的，磁盘存也是B-tree的；levelDB用lsm-tree方式存储。ob里的B-tree与lsm-tree是如何结合的？
ob使用的是LSM-Tree
核心结构
- MemTable 与 SSTable 分离：
- 所有写入操作首先在内存中的 MemTable 完成。
- 当 MemTable 达到一定大小时，数据会异步转储为磁盘上的 SSTable 文件（Sorted String Table）。
- 这部分结构体现了典型的 LSM-Tree 特性，即先将更新记录在内存中，再批量落盘，以减少随机 I/O 提升写入性能。
- 多层级的 SSTable 组织：
- OceanBase 将 SSTable 划分为三层：L0、L1、L2。
- L0 层使用 Tiered Compaction 模式（类似于 LevelDB），用于管理近期生成的小文件。
- L1、L2 层使用 Leveled Compaction 模式，将多个小文件合并为较大的文件，降低读取放大并提升查询效率。
- 这种混合的 Compaction 策略在一定程度上融合了 Tiered 与 Leveled 的优势，提高了整体性能。
如何借鉴 B-Tree 的特性？
虽然 OceanBase 使用的是 LSM-Tree 架构，但在某些关键模块引入了类似 B-Tree 的优化手段：
1. 宏块 (Macro Block) 与微块 (Micro Block)
- 数据文件按照 2MB 固定大小的宏块进行划分，每个宏块内部进一步拆分为不定长的微块。
- 这种分块方式类似于 B-Tree 中的 page/block 结构，便于对数据进行局部化管理和缓存优化。
- 宏块级别的重用机制也显著减少了合并期间的写放大问题。
2. 行列混合编码 + 压缩优化
- 对于列存场景，OceanBase 在 V4.3.0 版本引入了列存支持，并采用了行列混合编码。
- 数据按列维度分别进行编码（如字典编码、游程编码等），然后进行压缩。这种设计使得列存表可以像行存表一样处理事务操作，同时提升了 AP 场景下的压缩率和查询效率。
- 类似地，B-Tree 通过页内组织和索引结构优化数据访问效率，而 OceanBase 则通过编码与压缩策略达到类似效果。
3. 多级缓存机制
- OceanBase 引入了 Block Cache 和 Row Cache，避免频繁访问磁盘上的基线数据（SSTable）。
- 这一机制类似于 B-Tree 中的数据缓冲池（Buffer Pool），通过内存缓存加速热点数据访问。
4. 每日合并机制（Daily Major Compaction）
- 在每天业务低峰期，系统自动执行 Major Compaction，将所有的 MemTable、L0 Mini SSTable 和 L1 Minor SSTable 合并为一个新的 Major SSTable。
- 这种机制不仅清理了冗余数据，还优化了数据分布，类似于 B-Tree 中定期的 页重组或索引重建，以保持数据结构的紧凑性和查询效率。
1 个赞