【数据结构与算法】【算法思想】【算法总结】索引结构

深碍√TFBOYSˉ_ 2022-12-10 03:40 267阅读 0赞

> “基础不是100分考60分，而是建摩天大楼的地基。”

#### 为什么需要索引？ ####

（1）在实际的软件开发工作的本质都可以抽象为“对数据的存储和计算”。对应到数据结构和算法中，那“存储”需要的就是数据结构，“计算”需要的就是算法。  
（2）对于存储的需求，功能上无外乎增删改查。当存储的数据很多，性能就会成为这些系统要关注的重点，特别是在存储相关的基础系统、中间件中。  
（3）“如何节省存储空间、如何提高数据增删改查的执行效率”，解决这样的问题离不开索引

#### 索引的需求定义 ####

对于系统设计需求，一般可以从功能性需求和非功能性需求两方面来分析

##### 1. 功能性需求 #####

（1）数据是格式化数据还是非格式化数据？  
构建索引的原始数据，可分为两类：

*  一类是结构化数据，如MySQL 中的数据；
 *  一类是非结构化数据，如搜索引擎中网页。非结构化数据，一般需要预处理，提取出查询关键词，对关键词构建索引。

（2）数据是静态数据还是动态数据？

*  如果是一组静态数据，在构建索引时只需考虑查询效率
 *  动态数据构建索引，不仅要考虑索引的查询效率，在原始数据更新的同时，还需要动态地更新索引

（3）索引存储在内存还是硬盘？

*  当数据量小时，索引可以存储在内存中。
 *  原始数据量很大时，对应的索引可能也会很大。内存有限，可能需要将索引存储在磁盘中。
 *  第三种情况：一部分存储在内存，一部分存储在磁盘，这样可以兼顾内存消耗和查询效率。

（4）单值查找还是区间查找？

*  所谓单值查找，也就是根据查询关键词等于某个值的数据。
 *  所谓区间查找，就是查找关键词处于某个区间值的所有数据。不同的应用场景，查询的需求会多种多样。

（5）单关键词查找还是多关键词组合查找？

*  对于单关键词的查找，索引构建起来相对简单。
 *  多关键词查询要分多种情况:  
    A：像 MySQL 这种结构化数据的查询，可以实现针对多个关键词的组合，建立索引；  
    B：像搜索引擎这样的非结构数据的查询，可以针对单个关键词构建索引，然后通过集合操作，如求并集、求交集等，计算出多个关键词组合的查询结果。  
    不同的场景，不同的原始数据，对于索引的需求也会千差万别

#### 2. 非功能性需求 ####

（1）不管是存储在内存中还是磁盘中，索引**对存储空间的消耗不能过大**。

*  如果存储在内存中，索引对占用存储空间的限制就会非常苛刻
 *  如果存储在硬盘中，也不能掉以轻心，因为有时索引对存储空间的消耗会超过原始数据

（2）在考虑索引查询效率的同时，还要**考虑索引的维护成本**。

*  基于动态数据集合构建的索引要考虑索引的维护成本。因为在原始数据动态增删改的同时，也需要动态的更新索引。而索引的更新势必会影响到增删改操作的性能。

### 构建索引常用的数据结构有哪些？ ###

如散列表、红黑树、跳表、B+ 树，除此之外，位图、布隆过滤器可以作为辅助索引，有序数组可以用来对静态数据构建索引

*  散列表增删改查操作的时间复杂度是 O(1)，被一些键值数据库用来构建索引，如 Redis、Memcache。这类索引，一般都构建在内存中。
 *  红黑树是常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 O(logn)，也非常适合用来构建内存索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。
 *  B+ 树比起红黑树更加适合构建存储在磁盘中的索引  
    （1）B+ 树是一个多叉树，对相同个数的数据构建索引，B+ 树的高度要低于红黑树。  
    （2）当借助索引查询数据时，读取 B+ 树索引需要的磁盘 IO 次数会更少。  
    所以，如 MySQL、Oracle等，大部分关系型数据库的索引都是用 B+ 树来实现的
 *  跳表也支持快速添加、删除、查找数据，通过调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis 中的有序集合，就是用跳表来构建的
 *  布隆过滤器有一定的判错率，但可以规避它的短处，发挥它的长处  
    （1）尽管对于判定存在的数据可能并不存在，但是对于判定不存在的数据是一定不存在  
    （2）布隆过滤器有个大特点：内存占用非常少，所以可以针对数据，构建一个布隆过滤器存储在内存中。  
    （3）查询数据时，如果布隆过滤器判定数据不存在，就不必读取磁盘中的索引了。对于数据不存在的情况，数据查询就更加快速了。
 *  有序数组也可以被作为索引，如果数据是静态的只有查询操作，可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png