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

有关查询索引字段的信息，请查看如何索引数据库列。

解决方案

回答

为什么需要它？

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

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

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

什么是索引？

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

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

它是如何工作的？

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

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

注意：使用char代替varchar可以保证磁盘值的准确大小。
该示例数据库包含五百万行，并且没有索引。现在将分析几个查询的性能。这些是使用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字段是键字段，则对id字段进行线性搜索将需要平均" N / 2 = 500,000"次块访问才能找到一个值。但是由于id字段也已排序，因此可以执行二进制搜索，平均需要" log2 1000000 = 19.93 = 20"块访问。立刻我们可以看到这是一个巨大的进步。

现在，firstName字段既没有排序也不是键字段，因此二进制搜索是不可能的，值也不是唯一的，因此该表将需要搜索到末尾以进行精确的" N = 1,000,000"块访问。索引旨在纠正这种情况。

假定索引记录仅包含索引字段和指向原始记录的指针，则可以认为它会小于它指向的多字段记录。因此，索引本身比原始表需要更少的磁盘块，因此需要更少的块访问来进行迭代。下面概述了firstName字段上的索引的架构；

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

注意：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"个块访问，这与在非索引表。

什么时候应该使用？

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

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