一个经典的例子是“图书目录”

考虑一本1000页的“图书”，分为10个章节，每个部分包含100页。

很简单，对吧？

现在，想象一下你要找到一个包含单词“炼金术士”的特定章节。如果没有目录页，你只能浏览整本书/章节。也就是说：1000页。

这个类比在数据库世界中被称为“全表扫描”。

但是有了目录页，你就知道该去哪了！而且，要查找任何重要的章节，你只需要反复查看目录页。在找到匹配的索引后，您可以通过跳过其余内容来高效地转到该章节。

但是，除了实际的1000页之外，您还需要大约10页来显示索引，总共1010页。

因此，目录是一个单独的部分，用于存储索引列的值和指向排序顺序的索引行的指针，以进行高效查找。

在学校里，一切都很简单，对吧？:P

为什么需要索引？

当数据存储在基于磁盘的存储设备上时，它以数据块的形式存储。这些块被整体访问，因此成为原子磁盘访问操作。磁盘块的结构与链表类似；它们都包含数据部分、指向下一个节点（或块）位置的指针，并且不需要连续存储。

由于某些记录只能按一个字段排序，因此可以说在未排序字段上的搜索需要进行线性搜索，这需要平均 (N + 1) / 2 次块访问，其中 N 是表跨越的块数。如果该字段是非键字段（即不包含唯一条目），则必须在 N 次块访问下搜索整个表空间。

与排序字段相比，可以使用二分搜索，其块访问次数为 log2 N。而且，由于给定非键字段的数据已排序，因此一旦发现高值，就不需要搜索表中其余部分以查找重复值。因此性能提高非常大。

什么是索引？

索引是一种在多个字段上对一些记录进行排序的方式。在表的字段上创建索引会创建另一种数据结构，其中包含字段值和指向相关记录的指针。这个索引结构然后被排序，允许在其上执行二分搜索。

索引的缺点在于，这些索引需要磁盘上额外的空间，因为索引与 MyISAM 引擎一起存储在表中，如果在同一表中索引了许多字段，则该文件可以快速达到底层文件系统的大小限制。

它是如何工作的？

首先，让我们概述一个示例数据库表模式；

字段名              数据类型       磁盘上的大小
id（主键）         无符号INT       4字节
firstName           Char（50）      50字节
lastName            Char（50）      50字节
emailAddress    Char（100）    100字节

注意：char被用于替代varchar以允许准确的磁盘大小值。
这个示例数据库包含500万行，并且未被索引。现在将分析几个查询的性能。分别是使用id（排序关键字字段）和firstName（非关键字未排序字段）的查询。

示例1 - 排序和未排序字段的比较

考虑到我们的样本数据库有 r = 5,000,000 条固定大小的记录，每条记录长度为 R = 204 字节，它们存储在使用 MyISAM 引擎的表中，该引擎使用默认块大小 B = 1,024 字节。表的块因子将是 bfr = (B/R) = 1024/204 = 5 条记录每个磁盘块。容纳表所需的总块数是 N = (r/bfr) = 5000000/5 = 1,000,000 块。

在id字段上进行线性搜索需要平均 N/2 = 500,000 次块访问才能找到一个值，因为id字段是一个关键字段。但是由于id字段也是排序的，可以进行二分搜索，平均需要 log2 1000000 = 19.93 = 20 次块访问。我们可以立即看到这是一个巨大的改进。

现在firstName字段既不是排序字段也不是关键字段，因此不能进行二分搜索，值也不是唯一的，因此需要搜索表以获得精确的 N = 1,000,000 次块访问。这就是索引旨在纠正的情况。

考虑到索引记录只包含索引字段和指向原始记录的指针，因此它比指向的多字段记录小。因此，索引本身需要的磁盘块比原始表少，因此需要的块访问次数也少。下面概述了在firstName字段上创建的索引模式：

字段名          数据类型    磁盘上的大小
firstName       Char（50）   50个字节
（记录指针）     特殊         4个字节

注意：在MySQL中，指针长度为2、3、4或5个字节，具体取决于表的大小。

示例2：-建立索引

给定我们的样本数据库，其中包含r = 5,000,000条记录，索引记录长度为R = 54字节，并使用默认块大小B = 1,024字节。索引的分块因子为bfr =（B / R）=1024/54 = 18，每个磁盘块可以容纳bfr条记录。需要的块总数为N =（r / bfr）= 5000000/18 = 277,778 块。

现在，使用firstName字段进行搜索可以利用索引来提高性能。这允许对索引进行二进制搜索，平均需要log2 277778 = 18.08 = 19个块访问次数。为了找到实际记录的地址，需要另外一个块访问以读取，将总数增加到19 + 1 = 20块访问，相比之下， 在未索引的表中查找firstName匹配需要100万个块访问。

应该什么时候使用它？

考虑到创建索引需要额外的磁盘空间（以上例子中需要277,778个额外磁块，增加了大约28%），而过多的索引可能会引起文件系统大小限制问题，必须谨慎选择要索引的正确字段。

由于索引仅用于加速查找匹配记录中的字段，因此索引仅用于输出的字段将只是浪费磁盘空间和处理时间，而删除或插入操作时应避免使用。另外，鉴于二分查找的性质，数据的基数或唯一性很重要。对基数为2的字段建立索引将把数据分成两半，而基数为1,000的记录将返回大约1,000个记录。基数这么低将会降低效率，查询优化器如果基数少于记录数的30%，将会避免使用索引，从而使索引成为空间的浪费。