关键词定义

快速寻址

溯源需求，分为功能性和非功能性

功能性

  • 结构化数据还是非结构化（比如网页）
  • 静态数据还是非静态数据
  • 单值还是区间

  • 单关键词还是组合（交并补）

    非功能性

  • 存在内存（效率高总量少）还是硬盘(与内存相反)

  • 维护成本
  • 数据结构选型

常用类库索引案例说明

  • redis，mem cahe使用散列表，特点，查询快，复杂度O（1），为简单的键值对查询
  • ext文件系统使用红黑树，查询效率O（logn）
  • 关系型数据库比如mysql,oracle使用B+树，高度低于红黑树，io次数更少，适用于磁盘索引
  • redis有序集合，使用跳表，支持快速增删改节点

其他

  • 有序数组也可以作为索引，适用于静态数据，利用二分查找
  • 布隆过滤器可以用来辅助提升查询效率，当不存在时减少无效查询