图解：什么是索引？

╰+攻爆jí腚メ 2023-02-21 12:44 1阅读 0赞

# 1.磁盘 #

【图解】

`以一个拥有3个磁道和4个扇区的磁盘为例`  
![image][]

# 2.数据表与磁盘 #

【图解】

`以一个简单的用户表user_table为例，总共存储100行数据`  
![image][image 1]

*  每一个Block可以存储4行数据，那么该表需要占用25块磁盘；
 *  那么如果在该表中查询数据，最坏情况下据需要查询25块磁盘才能查到；
 *  需要注意的是，磁盘中的数据是无法直接处理的，需要读取到内存中处理，处理完成后再返回磁盘，即一次IO，那么在该表中查询，最坏的情况就是需要25次IO；

# 3.何为索引？ #

【图解】

`数据表index_table中只存储两列数据：id和地址指针，地址指针指向的是每行数据在磁盘中的位置`  
![image][image 2]

*  该数据表一行假设为16Byte，那么一Block可以存储32行，整个表占用4块（Block）；
 *  那么如果使用该数据表辅助查询，最坏情况需要查询4+1=5块（Block），即5次IO；
 *  相比较“没有该数据表辅助”的情况，效率大大提升，而该数据表就是所谓的“索引”

# 4.稀疏索引 #

【问题】

`但是上述方案并不足够好，如果用户表user_table中的数据不是100，而是1000的话，那么索引表index_table同样需要增加到1000，占用磁盘Block数为 1000/32 ≈ 31.3，向上取整32块（Block），那么最坏情况需要查询 32+1 = 33次，效率仍然不是很高。`

【解决方案】

`稀疏索引`

【图解】

`稀疏索引，也称作多级索引，在一级索引的基础之上，再加一层索引，但是稀疏索引不再是一一映射，而是一对多，即一行数据，映射一组数据（实际上就是一行数据中记录一组数据的最大值所在的位置）`  
![image][image 3]

*  稀疏索引假设一行为16Byte，那么一Block可以存储32行，整个表占用1块（Block）；
 *  所以最坏查询 1+1+1 = 3块（Block），即3次IO，这样效率就快得多。

[image]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlLzg3NjNGRkI4RTYyMDRGQ0JBQTlBMEQ4RjQ4MTE2NTM3LzE1NjM5?x-oss-process=image/format,png
[image 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlLzQ3QzA0RUM5NzJCNDRBQkY4MDUyNUQwNDI3MUE3NzE3LzE1NjQz?x-oss-process=image/format,png
[image 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlLzgyRTQwOEU2NzUwNjQ1RjBCMjE4RTBDMTQ5N0Y4NTA0LzE1NjQ1?x-oss-process=image/format,png
[image 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlL0VBRDc0QkFEOUQ3NDQwMTVBN0QzNzM4RUIxN0YwRTcwLzE1NjQ3?x-oss-process=image/format,png