如何使用SQLite3实现磁盘支撑的O(1)键存在性查询哈希表

当前查询慢的核心原因是没有给校验列建索引，SQLite每次查询都会遍历全表，按以下步骤调整可以大幅提升查询性能：

• 调整建表逻辑，直接将待校验列设为主键并使用WITHOUT ROWID参数，让表本身就是索引结构，避免额外的堆表存储开销：

  CREATE TABLE IF NOT EXISTS hashtable (val VARCHAR(34) PRIMARY KEY) WITHOUT ROWID;
  

  批量插入前可以先关闭索引、开启大容量缓存提升导入速度，插入完成后再重建索引。
• 优化查询语句，不要使用COUNT(1)统计匹配数，改用EXISTS语法，匹配到第一条符合条件的记录就直接返回结果，无需遍历所有匹配项：

  SELECT EXISTS(SELECT 1 FROM hashtable WHERE val = '待校验的键');
  

• 调整SQLite运行参数优化IO性能：将page_size调整为4KB/8KB匹配操作系统页大小，调大cache_size参数提升热点数据缓存命中率，开启WAL模式降低写入和查询的锁冲突。

如果调整SQLite后性能仍不符合预期，可以选择更适配存在性校验场景的存储方案：

• 布隆过滤器+KV存储组合：你当前的临时方案已经非常高效，可进一步调低布隆过滤器的误判率（比如设置为0.001%），仅在布隆过滤器返回命中时才触发磁盘查询，可大幅降低磁盘IO次数，整体查询效率接近O(1)。
• 嵌入式KV存储引擎：选择RocksDB、LevelDB这类面向磁盘优化的LSM树KV引擎，天生支持批量导入、点查，针对SSD/HDD的随机读做了大量优化，单节点点查QPS可达数万到数十万，远高于未优化的SQLite方案。
• 分片哈希方案：将所有34位键按前N位前缀分片，拆分到数百到数千个小文件中，每个小文件大小控制在可完全加载到内存的范围内，查询时先按前缀匹配到对应的分片文件，加载文件到内存后用哈希表校验，性能也可达到接近O(1)的水平。
• 排序后二分查找：将所有键排序后按固定大小分块存储，每个块存储块内首个键的前缀和块的磁盘偏移，查询时先通过前缀二分定位到对应块，再加载块内数据做二分查找，无需额外索引，存储开销比数据库方案低50%以上。

内容的提问来源于stack exchange，提问作者Trevor Hickey