索引定义
类比书籍的目录。通过目录，可以快速定位相关知识点的页数，查找的速度有质的提高。
索引的需求定义
功能性需求
数据是格式化数据还是非格式化数据。结构化数据，MySQL中的数据；非结构化数据，搜索引擎中网页。非机构化数据需要做预处理，提取出查询关键词，对关键词构建索引。数据是静态数据还是动态数据。静态数据，不会有数据的增加、删除、更新操作，构建索引时只需奥考虑查询效率。动态数据，在原始数据更新的同时，还需要动态的更新索引。
索引存储在内存还是硬盘。存储在内存，查询速度高。原始数据量大，索引很大，内存有限，需要将索引存储在磁盘。一部分存储在内存，一部分存储在磁盘，可以兼顾内存消耗和查询效率。
单值查找还是区间查找。单值查找，根据查询关键词等于某个值的数据。区间查找，查找关键词处于某个区间值的所有数据。
单关键词查找还是多关键词组合查找。多关键词查询：结构化数据，针对多个关键词的组合建立索引；非结构化数据，针对单个关键词构建索引，然后通过集合操作（并集、交集），计算出多个关键词组合的查询结果。
非功能性需求
不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大。索引对存储空间的消耗可能会超过原始数据。在考虑索引查询效率的同时，还要考虑索引的维护成本。在原始数据动态增删改的同时，也需要动态的更新索引，索引的更新势必会影响到增删改操作的性能。
构建索引常用的数据结构
散列表、红黑树、跳表、B+树，可以作为动态数据集合的索引，位图、布隆过滤器可作为辅助索引，有序数组可以用来对静态数据构建索引。
散列表增删改查的时间复杂度为O(1)，一般构建在内存中。如键值数据库（Redis、Memcache）的索引。
红黑树数据插入、删除、查找的时间复杂度为O(logn)，适合构建内存索引。如Ext文件系统中，对磁盘块的索引。
B+树相比红黑树，更适合构建存储在磁盘中的索引，需要的磁盘IO次数更少。如关系型数据库MySQL、Oracle的索引。
跳表支持快速添加、删除、查找数据，通过灵活调整索引结点个数和数据个数之间的比例，可以很好的平衡索引堆内存的消耗及其查询效率。如Redis中的有序集合的索引。
位图和布隆过滤器，辅助存储在磁盘中的索引，加速数据查找的效率。
布隆过滤器有一定的判错率。对于判定存在的数据，可能并不存在；对于判定不存在的数据，则肯定不存在。但内存占用非常少。
针对数据，构建一个布隆过滤器，存储在内存中，当要查询数据的时候，可以先通过布隆过滤器，判定是否存在。若不存在，则没有必要读磁盘中的索引，对于数据不存在的情况，数据查询更加快速。
有序数组。静态数据，没有插入、删除、更新操作，可以把数据查询用的关键词抽取出来，组织成有序数据，然后利用二分查找算法来快速查找数据。