为什么需要索引

1. 实际软件开发中，需求的本质是对数据的存储和计算
   • 数据的存储，需要的是“数据结构”
   • 数据的计算，需要的是“算法”
2. 对数据存储的需求
   • 增删改查，以及提高这些操作的执行效率
   • 节省存储空间

“索引”的需求分析

功能性需求

1. 构建索引的原始数据的格式
   • 结构化数据，如 MySQL 中的数据
   • 非结构化数据，如搜索引擎中的网页等，需要做预处理，提取出查询关键词，对关键词构建索引
2. 操作数据的类型
   • 静态数据，构建索引时只需要考虑数据查询时的效率
   • 动态数据，构建索引时，需要考虑数据查询、数据更新（动态的更新索引）的效率
3. 数据存储的位置
   • 内存，查询数据的速度快，但是存储的数据量有限
   • 硬盘，查询数据的速度慢，支持大量数据的存储
   • 内存 + 硬盘
4. 数据的查找方式
   • 单值查找，根据某个关键词等于某个值的数据查找
   • 区间查找，查找关键词处于某个区间值内的数据
   • 单关键词查找
   • 多关键词组合查找
     • 如果是结构化数据，如 MySQL，可以针对多个关键词的组合建立联合索引
     • 如果是非结构化数据，如 网页内容，可以对多个关键词分别建立索引，在查询的时候取交集、并集等，计算出多个关键词组合的查询结果

非功能性需求

1. 索引不能消耗过多的存储空间，或者远超过原始数据，否则本末倒置
2. 在考虑索引的查询效率的同时，也要考虑到索引的维护成本

构建索引常用的数据结构

散列表

1. 增删改查的时间复杂度为 O（1）
2. 常用于键值数据库中，如 Redis、Memcache
3. 常构建在内存中

红黑树

1. 数据的插入、删除、查找的时间复杂度为 O（logn）
2. 常构建在内存中
3. Ext 文件系统中，对磁盘块的索引，使用的是红黑树

B+ 树

1. B+ 树需要操作的磁盘 IO 更少
2. 常构建在硬盘上
3. 大部分关系型数据库的索引都是用 B+ 树来实现的，如 MySQL、Oracle

跳表

1. 通过调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及查询效率
2. 常构建在内存中
3. Redis 中，有序集合的底层实现，使用的是跳表

辅助类数据结构，快速判断数据是否在索引中

1. 位图
2. 布隆过滤器，利用“不存在的一定不存在”规则