数据库索引如何工作？

Question

鉴于索引随着数据集的增加而变得非常重要，有人可以解释在数据库不可知的级别上索引是如何工作的吗？

Answer 1

为什么需要它？

当数据存储在基于磁盘的存储设备上时，它将作为数据块存储。完全访问这些块，使它们成为原子磁盘访问操作。磁盘块的结构与链接列表几乎相同。两者都包含一个数据节，一个指向下一个节点（或块）位置的指针，并且都不需要连续存储。

由于许多记录只能在一个字段上排序，因此我们可以说，在未排序的字段上进行搜索需要进行线性搜索，该搜索需要进行N/2块访问（平均），其中N，块的数量是该表跨度。如果该字段是非关键字段（即不包含唯一条目），则必须在N块访问时搜索整个表空间。

而对于已排序的字段，可以使用具有log2 N块访问权限的二进制搜索。同样，由于给定的非键字段对数据进行了排序，因此一旦找到更高的值，就无需在表的其余部分中搜索重复的值。因此，性能的提高是巨大的。

什么是索引？

索引是对多个字段上的多个记录进行排序的一种方式。在表中的字段上创建索引会创建另一个数据结构，该数据结构将保留字段值以及指向与其相关的记录的指针。然后对该索引结构进行排序，从而允许对其执行二进制搜索。

索引的不利之处在于，由于使用MyISAM引擎将索引一起存储在表中，因此这些索引需要磁盘上的额外空间，如果对同一表中的许多字段进行了索引，则此文件可以快速达到基础文件系统的大小限制。

它是如何工作的？

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

字段名称数据类型磁盘大小
id（主键）无符号INT 4字节
firstName Char（50）50个字节
姓氏Char（50）50字节
emailAddress Char（100）100字节

注意 ：使用char代替varchar可以保证磁盘值的准确大小。该示例数据库包含五百万行，并且没有索引。现在将分析几个查询的性能。这些是使用
id （已排序关键字字段）的查询，以及使用 firstName （非关键未排序字段）的查询。

实施例1 - 排序VS未排序的字段

给定我们的样本数据库，r = 5,000,000记录大小固定，给出记录的R = 204字节长度，并且使用MyISAM引擎将它们存储在表中，该引擎使用默认的块大小B = 1,024字节。该表的阻塞因素将是bfr = (B/R) = 1024/204 = 5每个磁盘块的记录。保存该表所需的总块数为N = (r/bfr) = 5000000/5 = 1,000,000块。

N/2 = 500,000假定id字段是键字段，则对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每个磁盘块的记录。保持索引所需的总块数为N = (r/bfr) = 5000000/18 = 277,778块。

现在，使用 firstName 字段进行的搜索可以利用索引来提高性能。这允许使用log2 277778 = 18.08 = 19块访问的平均值对索引进行二进制搜索。要查找实际记录的地址，这需要进一步的块访问来读取，从而使总数进入19 + 1 = 20块访问，这与在非索引表中查找 firstName 匹配所需的1,000,000块访问相差甚远。

什么时候应该使用？

鉴于创建索引需要额外的磁盘空间（上例中增加了277,778个块，增加了约28％），并且索引过多会导致文件系统大小限制引起的问题，因此必须谨慎选择正确的磁盘空间。要索引的字段。

由于索引仅用于加速记录中匹配字段的搜索，因此可以推断出，仅用于输出的索引字段在进行插入或删除操作时只会浪费磁盘空间和处理时间，因此应该避免。同样，鉴于二进制搜索的性质，数据的基数或唯一性也很重要。在基数为2的字段上建立索引将把数据分成两半，而基数为1,000的索引将返回大约1,000条记录。由于基数如此之低，有效性降低到了线性排序，并且如果基数小于记录数的30％，查询优化器将避免使用索引，有效地使索引浪费了空间。