我们知道，磁盘的读写效率是比较低的，以传统机械硬盘为例，读写时涉及到读写头的寻道和定位，这部分时间开销可能比实际读写数据时所花的时间还要长。即使是固态硬盘，由于数据的存储可能是散落在各个磁盘块中，通过指针连接起来，因此访问数据时需要对磁盘进行多次读写，同样会带来效率上的问题。
再来看数据库的存储，数据库中的一个表可能存储在多个文件中，而每个文件包含了多个磁盘块(扇区)，我们讨论最好的情况，也就是所有记录都是按查询的字段进行排序，那么此时可以利用二分法等高效的算法进行搜索。如果是在内存中进行这种搜索，log(n) 的时间确实非常高效，但放在磁盘中就未必了，为什么这么说?
因为这些高效算法通常都是在内存中操作的，也就是说数据都已经被加载到内存中。而一个表中包含的数据量可能很大，没办法将这些数据一次性装载到内存中，因此我们需要通过多次读写磁盘来完成这些操作。这样一来，磁盘本身的文件组织方式就会对算法的效率造成影响。
比如我们用二分法来查找数据，二分法是建立在数据能够被随机访问的基础上的，这样可以计算出中间，并直接访问该。如果磁盘块是连续的还好，假设每条记录定长，那么我们可以得到中间的扇区号，直接访问该扇区，从而得到目标记录;但如果磁盘块不连续，那么只能通过指针进行连接，这样我们就没办法直接得出中间的扇区号，只能从第一个磁盘块开始，依次访问它的下一个磁盘块，也就是顺序访问，即使记录是有序的，二分法也没有用武之地，只能从头遍历记录进行查找。
总结上述提到的问题，就是当数据量大的时候，数据无法被一次性加载到内存中，因此对数据的查找操作受限于文件在磁盘中的存储方式，特别是利用指针来连接不连续磁盘块的情况，极大影响查询效率。
我们是根据什么来找到索引项的?对了，是字。因此字就是用于索引的字段，叫做 索引字段，页码相当于一条记录的实际存储地址，等价于指向记录所在磁盘的指针。
索引的意义，就在于它只抽取了原记录中的一部分关键的信息，并与记录的建立关联，以此定位记录在磁盘上的真正。
索引存储的数据较少，更容易被加载到内存中，也就意味着我们可以通过高效的算法在索引上查找目标记录的索引项，得到目标记录在磁盘上的，然后直接读取该记录。
例如以字段 A 作为索引，那么每个索引项只存 A 的值，以及 A 对应记录所在磁盘的。这样一来，我们通常可以将索引文件加载到内存中，然后根据询记录字段 A 的值，找到索引项，得到该记录在磁盘中的，就能直接到特定磁盘块将目标记录读取出来。
稀疏索引只包含了索引字段中一部分的值，通过这些值可以确定目标记录的范围，然后再到这个范围中顺序查找。因此，稀疏索引要求主文件必须按照索引字段进行排序，通常索引文件本身也有相同的排序关系。
下面会讲到主索引，它是一种特殊的稀疏索引，它的索引项并不是指向记录，而是指向记录所在的存储块。也就是说，一个存储块对应一个索引项。
因为索引字段值相同的记录是连续放在一起的，因此索引项只需指向索引字段值相同记录中的第一条记录。
这里引入了一个中间层。因为主文件中索引字段值存在重复，并且没有按照索引字段排序，因此必须对每条记录建立一个索引，才能由索引文件找到主文件中的记录。但是由于索引中不包含重复值，因此我们可以引入一个中间层，让索引项不直接指向记录，而是指向中间层。中间层的指针桶与记录一一对应，并且索引字段值相同的记录对应的指针桶是连续存放的，这样就等价于中间层是按索引字段进行排序。
要么索引不重复，这就要求索引指向的结构是按索引字段排序的(中间层也可以认为是按索引字段排序)，这样才可以仅仅指向索引字段值相同记录中的第一条记录。
辅助索引是稠密索引，它是建立在一个或多个非排序字段上的辅助存储结构，通常不同的索引字段值对应一个索引，如果有重复的索引字段值，则用类似链表的结构来存储具有相同索引字段值记录的，也就是前面提到的引入中间层的策略。
如果主文件的某一排序字段取值不唯一，那么该字段就称为聚簇字段。聚簇索引通常定义在聚簇字段上;
这篇文章对索引进行了概括性的介绍，说明了索引在数据库查询中的意义，并介绍了索引的几种分类方式。
本文来源于ipfs