查找对应的 SSTable 文件

简介: 通过分层结构与二分查找快速定位SSTable,结合BloomFilter过滤和索引区加速查询。利用table cache与block cache缓存机制,减少磁盘IO,提升检索效率。整个过程高效有序,适用于大规模数据检索场景。(238字)

何查找对应的 SSTable 文件

在理解了这样的架构之后,我们再来看看当我们想在磁盘中查找一个元素时,具体是怎么操作的。

首先,我们会在 Level 0 层中进行查找。由于 Level 0 层的 SSTable 没有做过多路归并处理,它们的覆盖范围是有重合的。因此,我们需要检查 Level 0 层中所有符合条件的 SSTable,在其中查找对应的元素。如果 Level 0 没有查到,那么就下沉一层继续查找。

而从 Level 1 开始,每一层的 SSTable 都做过了处理,这能保证覆盖范围不重合的。因此,对于同一层中的 SSTable,我们可以使用二分查找算法快速定位唯一的一个 SSTable 文件。如果查到了,就返回对应的 SSTable 文件;如果没有查到,就继续沉入下一层,直到查到了或查询结束。

查找所有符合条件的SSTableLevel0(4个)SSTableSSTableSSTableSSTable二分查找对应的SSTable(10M)Level1SSTableSSTableSSTableSSTableSSTable二分查找对应的SSTable(100M)SSTableSSTableLevel2SSTableSSTableSSTableLevel6(1T)SSTableSSTableSSTableSSTableSSTable

可以看到,通过这样的一种架构设计,我们就将 SSTable 进行了有序的管理,使得查询操作可以快速被限定在有限的 SSTable 中,从而达到了加速检索的目的。

SSTable 文件中的检索加速

那在定位到了对应的 SSTable 文件后,接下来我们该怎么查询指定的元素呢?这个时候,前面我们学过的一些检索技术,现在就可以派上用场了。

首先,LevelDB 使用索引与数据分离的设计思想,将 SSTable 分为数据存储区和数据索引区两大部分。

DatablockDatablockDatablock数据存储区blockData过滤器数据区:支持多个过滤器,目前只有一个Bloomfilter过滤器Datablock过滤器索引区:当存在多个过滤器时,Filterblock对过滤器进行索引数据索引:对数据存储区的block进行索引,Filterblock格式:数据索引区KeyoffsetsizeMetalndexblockIndexblock记录lndexblock和Metalndexblock的位置和大小Footblock

我们在读取 SSTable 文件时,不需要将整个 SSTable 文件全部读入内存,只需要先将数据索引区中的相关数据读入内存就可以了。这样就能大幅减少磁盘 IO 次数。

然后,我们需要快速确定这个 SSTable 是否包含查询的元素。对于这种是否存在的状态查询,我们可以使用前面讲过的 BloomFilter 技术进行高效检索。也就是说,我们可以从数据索引区中读出 BloomFilter 的数据。这样,我们就可以使用 O(1) 的时间代价在 BloomFilter 中查询。如果查询结果是不存在,我们就跳过这个 SSTable 文件。而如果 BloomFilter 中查询的结果是存在,我们就继续进行精确查找。

在进行精确查找时,我们将数据索引区中的 Index Block 读出,Index Block 中的每条记录都记录了每个 Data Block 的最小分隔 key、起始位置,还有 block 的大小。由于所有的记录都是根据 Key 排好序的,因此,我们可以使用二分查找算法,在 Index Block 中找到我们想查询的 Key。

那最后一步,就是将这个 Key 对应的 Data block 从 SSTable 文件中读出来,这样我们就完成了数据的查找和读取。

利用缓存加速检索 SSTable 文件的过程

在加速检索 SSTable 文件的过程中,你会发现,每次对 SSTable 进行二分查找时,我们都需要将 Index Block 和相应的 Data Block 分别从磁盘读入内存,这样就会造成两次磁盘 I/O 操作。我们知道磁盘 I/O 操作在性能上,和内存相比是非常慢的,这也会影响数据的检索速度。那这个环节我们该如何优化呢?常见的一种解决方案就是使用缓存。LevelDB 具体是怎么做的呢?

针对这两次读磁盘操作,LevelDB 分别设计了 table cache 和 block cache 两个缓存。其中,block cache 是配置可选的,它是将最近使用的 Data Block 加载在内存中。而 table cache 则是将最近使用的 SSTable 的 Index Block 加载在内存中。这两个缓存都使用 LRU 机制进行替换管理。

那么,当我们想读取一个 SSTable 的 Index Block 时,首先要去 table cache 中查找。如果查到了,就可以避免一次磁盘操作,从而提高检索效率。同理,如果接下来要读取对应的 Data Block 数据,那么我们也先去 block cache 中查找。如果未命中,我们才会去真正读磁盘。

这样一来,我们就可以省去非常耗时的 I/O 操作,从而加速相关的检索操作了。

相关文章
|
存储 缓存 Oracle
|
11月前
|
存储 搜索推荐 索引
跳表法加速倒排索引
跳表、哈希表与位图法可加速倒排索引。跳表通过多层链表实现快速跳转,将归并查找时间降至O(log n);哈希表适用于小集合查大集合,查询可达O(1);位图则利用位运算高效求交集,适合短posting list场景,显著提升检索效率。
|
11月前
|
存储 Serverless
哈希冲突
哈希冲突可通过优化哈希函数或采用冲突解决策略应对。开放寻址法通过线性、二次探查或双散列寻找空位,但易导致聚集,影响效率;链表法则在冲突位置构建链表,避免抢占,更适应动态数据,是常用方案之一。
|
7月前
|
人工智能 IDE 架构师
AI 编程工具唯一推荐 Claude Code:但实名认证的这道门槛,让人笑不出来
JeecgBoot AI专题研究 为什么 2026 年 AI 编码只推荐 Claude Code,以及最近实名认证政策带来的真实焦虑 一句话结论:不要再纠结了如果你是一个正在 2026 年做技术决策的开发者、CTO 或者架构师,正在犹豫 AI 编码工具该选谁,我的建议很直接:别想太多,先用 Cl
826 1
AI 编程工具唯一推荐 Claude Code:但实名认证的这道门槛,让人笑不出来
|
7月前
|
人工智能 小程序 前端开发
AI开发实战4、AI总是忘记项目规范?因为你缺了这份终极上下文文件
本文是AI编程实战系列第4篇,聚焦前端开发,详解如何用`CLAUDE.md`(AI专属项目指南)提升AI编码准确性与一致性——涵盖上下文构建、规范统一、效率提升与幻觉抑制。下篇将切入go-zero后端接口开发。(239字)
937 0
AI开发实战4、AI总是忘记项目规范?因为你缺了这份终极上下文文件
|
7月前
|
存储 人工智能 自然语言处理
让你的 Claude Code 拥有长久记忆能力
Claude-Mem 是专为 Claude Code 设计的开源持久记忆插件:自动捕获工具操作、生成语义摘要、跨会话智能注入上下文;支持自然语言搜索、可视化界面、隐私控制与全文检索,让 AI 真正“记住项目、越用越懂你”。(239字)
2353 1
|
8月前
|
人工智能 JSON 架构师
Superpowers:Vibe Engineering 的第一站——让 Coding Agent 守点规矩
Vibe Coding追求快速迭代,但易致设计缺失、测试不足、行为不稳;Superpowers提出Vibe Engineering新范式,通过14项强制“技能”(如设计评审、TDD、子代理审查等),将工程纪律固化为AI必遵流程,实现“能跑也敢上线”。
1910 1
|
8月前
|
人工智能 JavaScript 测试技术
实战复盘:我是如何把 Claude Code 的月账单从 $800 砍到 $150 的
用 Claude Code 做开发确实爽,但月底看到账单的时候就不爽了。 我手上有一个 5 万行左右的 TypeScript 项目,刚开始放开了用,一个月下来直接烧掉 $800。这个数字让我不得不坐下来认真研究一下——钱到底花在哪了?有没有办法在不影响开发效率的前提下,把成本打下来? 经过一个月的摸索和调优,最终月费稳定在 $150 左右,降幅达到 81%。这篇文章就是这段经历的完整总结。 很多人以为 AI 编程助手的开销主要在"它给你写的代码"上,其实不然。我拿自己的项目做了统计,结果挺意外的:
3282 5
|
11月前
|
存储 弹性计算 人工智能
大模型应用开发
大模型应用开发指通过API与大模型交互,构建智能化应用。不同于传统Java开发,其核心在于调用部署在云端或本地的大模型服务。企业可选择开放API、云平台或本地服务器部署,各具成本、安全与性能权衡。本章将详解部署方式与开发实践,助你快速入门。