实体ID快速查询适用的数据结构、算法及持久化数据库选型

算法与对应数据结构 #

针对唯一ID的快速查询需求，最优选择是哈希算法，对应数据结构为哈希表（散列表）：

• 哈希算法可将任意长度的唯一ID映射为固定长度的哈希值，直接通过哈希值定位数据存储位置，平均查询时间复杂度为O(1)，工业界成熟实现会通过链地址法、开放寻址法等方案优化哈希冲突问题，实际使用中查询效率基本可以拉满。
• 大部分编程语言内置的Set结构底层就是哈希表实现，比如Python的set、Java的HashSet、Go的map[IDType]struct{}，原生支持快速的ID存在性校验和读取，不需要自己手动实现。
• 如果你后续有范围查询、排序的额外需求，可以替换为跳表或者B+树，这两种数据结构查询时间复杂度为O(log n)，同时支持顺序扫描，比哈希表适配场景更广。

支持持久化与崩溃恢复的数据库工具 #

可以根据业务规模和使用场景选择：

• 高性能缓存/存储场景选Redis

  Redis原生支持Set数据类型，底层同样基于哈希表实现，查询性能极高，支持RDB快照、AOF日志两种持久化机制，调整AOF刷盘策略后可做到崩溃后几乎零数据丢失，持久化文件直接落地磁盘，适合读写性能要求高的场景。

• 强一致性、结构化存储场景选关系型数据库
  比如MySQL、PostgreSQL，将实体ID设为主键或者添加唯一索引即可，主键索引底层为B+树，查询效率满足绝大多数业务需求，支持ACID特性，天然具备持久化能力和崩溃恢复机制，适合需要关联查询、强数据一致性的场景。
• 轻量本地存储场景选SQLite
  单文件型轻量数据库，不需要额外部署服务，支持主键索引快速查询，自带崩溃恢复机制，适合嵌入式、客户端本地应用场景。
• 超大规模分布式存储场景选分布式KV数据库
  比如HBase、Cassandra，底层基于LSM树实现，支持主键的毫秒级查询，自带多副本冗余存储，服务崩溃、节点故障都能自动恢复数据，可支撑PB级别的数据存储。

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