m数据结构 day19 查找（二）索引查找（稠密索引，分块索引，倒排索引）

小灰灰 2023-02-11 08:45 28阅读 0赞

索引查找广泛用于**文件检索，数据库和搜索引擎**等领域。

### 文章目录 ###

*  索引：为加快查找速度而设计的一种数据结构
 *  三种线性索引
 *   *  稠密索引：索引项一定有序
     *   *  优缺点
     *  分块索引：数据集分块有序，每一块对应一个索引，块内无序，块间有序
     *   *  索引项结构
         *  块间有序查找（快）+块内顺序查找（慢）：所以时间复杂度介于顺序查找和有序查找之间
         *  计算分块索引的平均查找长度
         *  优缺点
     *  倒排索引 inverted index
     *   *  用一个例子讲解
         *  名字的由来
         *  优缺点
         *  记录号表的改进方向

第一篇关于查找的文章介绍了一种最基础的无序查找（顺序查找，是最基础的也最费时间的查找方法，是海量数据查找表的福音）和三种有序查找，本文继续讲无序查找，因为现实中的很多场景涉及到**海量数据**，比如服务器的日志信息，论坛的帖子以及回复等，一天百万千万条，对这种大规模大体量的数据**基于某个关键字排序的时间代价极为昂贵**，所以这类海量数据并不排序，而是直接**以时间先后顺序存储**。这种情况下，必须设计一种时间复杂度比顺序查找低的无序查找算法。

这就是本文主角，索引查找。索引是个好东西，在计算机科学中广泛使用，尤其是**磁盘文件和大型数据库**中更加常用。

本文讲解的很粗浅，深度不够，只是抛砖引玉。现实中应用的搜索技术是非常复杂的，本文这些是最经典最基本的方法，在现实中还需要改善。

# 索引：为加快查找速度而设计的一种数据结构 #

设计各种数据结构是为了存储数据和提高处理数据的速度（通过存储数据之间的逻辑关系实现）。索引，就是一种为了提快无序查找表中的关键字查找速度，而专门设计的数据结构，但是我们从小到处接触索引，所以它又是特别熟悉的，现在带着更专业的眼光去看待它吧。

![在这里插入图片描述][20200522154210730.png]

按照结构，索引有**线性索引，树形索引和多级索引**三种。

本文只介绍了线性索引，即**把所有索引项**（数据）**构成的集合组织为线性结构**，所以**线性索引**又称**索引表**。

# 三种线性索引 #

## 稠密索引：索引项一定有序 ##

![在这里插入图片描述][20200522154228395.png]  
比如excel表格，生活中的表格数据条目相对较少，不会达到百万千万条，所以基本都使用稠密索引。

稠密索引的**索引项一定是有序的**。如下图，因为建立索引的目的是加快查找，只有索引项是有序的（比如下图就是按照关键码的大小给关键码编索引号），才能利用有序查找等，得到快的查找速度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]

### 优缺点 ###

*  优点：
 *  缺点：空间代价大。索引数目和数据记录数一样多，如果数据集规模很大，比如上亿，那么索引也很大，很占内存。  
    分块索引就改善了这个缺点，减少了索引的数目。

## 分块索引：数据集分块有序，每一块对应一个索引，块内无序，块间有序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]  
总之，有序需要付出时间和空间的代价，但是可以换来效率。

例子：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]

### 索引项结构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]

### 块间有序查找（快）+块内顺序查找（慢）：所以时间复杂度介于顺序查找和有序查找之间 ###

快慢结合，有序和无序结合  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]

### 计算分块索引的平均查找长度 ###

假设数据集有n条记录，被平分为m块（计算平均查找长度，所以平分），每块有t个记录。则 n = m ∗ t n=m\*t n=m∗t

*  查找索引表（即存了索引的线性表，并不是数据集哦）的平均查找长度 L b L\_b Lb：索引表长度是m，可以有序查找，根据最好（查找长度为1）和最差（查找长度为m）的等概率原则， L b = m + 1 2 L\_b=\\frac\{m+1\}\{2\} Lb=2m\+1
 *  块内查找记录的平均查找长度 L w L\_w Lw：只能顺序查找，也是考虑等概率原则，所以 L w = t + 1 2 L\_w=\\frac\{t+1\}\{2\} Lw=2t\+1
 *  分块索引的平均查找长度  
     A S L w = L b + L w = t + m 2 + 1 = t + n t 2 + 1 ASL\_w = L\_b+L\_w=\\frac\{t+m\}\{2\}+1=\\frac\{t+\\frac\{n\}\{t\}\}\{2\}+1 ASLw=Lb\+Lw=2t\+m\+1=2t\+tn\+1

转换为只依赖块内记录数t和数据记录总数n的式子后，可以看到，当t等于 n \\sqrt n n时，即块内记录数t等于块数m时，平均长度最短（最佳情况），为 n + 1 \\sqrt n +1 n\+1。

### 优缺点 ###

*  优点：

1.  减少了索引数目；
2.  比纯顺序查找快得多，作为无序查找算是很好了（当然，是结合了有序查找的）。这种块内无序的工作方式，相比于顺序查找，大大提升了查找效率，所以**数据库的查找**常用分块查找。

*  缺点：比纯有序查找慢，这个缺点属于鸡蛋里挑骨头啦

## 倒排索引 inverted index ##

最基础的，最简单的查找算法。

> 前阵子看知乎，刷到一个人的面经， 面试官问的就是为什么搜索引擎可以那么快返回给我们搜索结果，当时作者没答出来，后来他才知道，就是倒排索引！！！问题地址懒得找了，知乎上关于搜索引擎比如Google和百度为什么那么快有很多讨论和回答，已经探讨到很深入的地步了，不仅仅是倒排索引算法了，还讲到了分布式数据库和缓存等，自行搜索食用。

### 用一个例子讲解 ###

假设有两篇文章（这里为了举例，每篇文章实际就是一句话），分别放在两个网页

![在这里插入图片描述][20200522194024416.png]  
那么搜索引擎就会去把所有文章中的所有单词找出来，然后建立一个下面这样的表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]  
当你在搜索框键入一个单词，比如good时，由于单词是有序存放的，很快可以找到good，也就找到了含有这个单词的文章编号，于是搜索引擎立即把这些文章编号对应的网页排序后返回过来，当然也会返回共找到2条记录。

就因为提前把文章编号存起来了，存在了索引项里，所以一搜索立刻就返回回去了，是就像为每个问题都早已准备好了答案。  
![在这里插入图片描述][20200522193737301.png]

### 名字的由来 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 7]

### 优缺点 ###

*  优点：查找速度非常快，因为一旦生成索引表，就只需花费在索引表中查找索引项的时间了，直接返回记录号数的的时间都可以忽略。
 *  缺点：

1.  记录号表不是定长的，因此插入和删除等维护操作比较困难；
2.  只能告诉我们在哪些文章中出现过，但是无法查找到具体出现的位置。如果要知道具体在哪里出现，还需要进一步改良记录号表

### 记录号表的改进方向 ###

1.  如果文章记录上亿，搜索引擎返回记录号时，不会都返回大的数字，因为太占空间了，而会使用一点压缩技术  
    ![在这里插入图片描述][20200522200633352.png]
2.  中文文章更复杂，比如搜索“中国人”，则“中国”，“国人”都是可能的关键词。

[20200522154210730.png]: https://img-blog.csdnimg.cn/20200522154210730.png
[20200522154228395.png]: https://img-blog.csdnimg.cn/20200522154228395.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200522183548292.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200522184437642.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200522185503811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200522185250208.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200522185319927.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200522185347535.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200522194024416.png]: https://img-blog.csdnimg.cn/20200522194024416.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200522194044920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200522193737301.png]: https://img-blog.csdnimg.cn/20200522193737301.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200522194947327.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200522200633352.png]: https://img-blog.csdnimg.cn/20200522200633352.png