Sorted string tables (SST) from first principles
4 months ago
- #database
- #storage
- #performance
- SSD与内存：理解数据如何从SSD提取到内存对数据库性能至关重要
- 存储设备上的页：SSD以4KB页为单位读取数据，因此空间局部性和时间局部性对减少读取放大非常重要
- SSD上的不可变性：由于块级数据重写的开销，SSD更适合不可变数据结构
- SSD持久化存储：日志和SST等不可变的、批量对齐的数据结构是SSD的理想选择
- 排序字符串表(SST)：SST按键排序存储数据，支持高效二分查找并充分利用空间局部性
- 数据块：SST数据块按键排序并编码，以实现高效的磁盘存储和检索
- 索引：SST使用索引快速定位数据块，避免扫描整个文件
- 过滤器索引：布隆过滤器和最小/最大过滤器可在访问数据块前判断键是否存在于SST中
- 元数据块：存储索引块和过滤器块位置等关键信息
- SST作为通用构建块：通过巧妙的键编码，SST可以建模多种数据访问模式
- 键编码策略：命名空间、复合键、二级索引等技术使SST能灵活建模数据
- SST的重要性：SST充分发挥SSD和对象存储优势，成为众多数据库系统的核心基础组件