Sql 数据库索引如何工作

Why is it needed?

当数据存储在基于磁盘的存储设备上时，它被存储为数据块.这些块全部被访问，使它们成为原子磁盘访问操作.磁盘块的 struct 与链表基本相同；两者都包含一个数据段，一个指向下一个 node (或块)位置的指针，并且都不需要连续存储.

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

而对于排序字段，可以使用二进制搜索，它有log2 N个块访问.此外，由于数据是在给定非键字段的情况下进行排序的，因此一旦找到更高的值，就不需要在表的其余部分搜索重复的值.因此，性能的提高是巨大的.

What is indexing?

索引是对多个字段上的多个记录进行排序的一种方法.在表中的字段上创建索引将创建另一个数据 struct ，该 struct 保存字段值以及指向该字段相关记录的指针.然后对该索引 struct 进行排序，允许对其执行二进制搜索.

索引的缺点是，这些索引需要额外的磁盘空间，因为索引是使用MyISAM引擎存储在一个表中的，如果同一个表中的许多字段都被索引，这个文件可以很快达到基础文件系统的大小限制.

How does it work?

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

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

Note:char被用来代替varchar，以便在磁盘上获得准确的大小值.

100 - sorted vs unsorted fields

假设我们的示例数据库包含r = 5,000,000条固定大小的记录，记录长度为R = 204字节，它们使用MyISAM引擎存储在一个表中，MyISAM引擎使用默认的块大小B = 1,024字节.该表的阻塞因子 for each 磁盘块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

Note:MySQL中的指针长度为2、3、4或5字节，具体取决于表的大小.

100 - indexing

假设我们的示例数据库包含r = 5,000,000条记录，索引记录长度为R = 54字节，使用默认块大小为B = 1,024字节.索引的阻塞因子 for each 磁盘块bfr = (B/R) = 1024/54 = 18条记录.保存索引所需的总块数为N = (r/bfr) = 5000000/18 = 277,778块.

现在，使用firstName字段的搜索可以利用索引来提高性能.这允许对索引进行二进制搜索，平均有log2 277778 = 18.08 = 19个块访问.要找到实际记录的地址，需要进一步的块访问才能读取，使总数达到19 + 1 = 20个块访问，这与在非索引表中找到firstName个匹配项所需的log2 277778 = 18.08 = 190000个块访问相go 甚远.

When should it be used?

鉴于创建索引需要额外的磁盘空间(上述示例中有277778个额外的块，增加了约28%)，并且过多的索引可能会导致文件系统大小限制引起的问题，因此必须仔细考虑 Select 要索引的正确字段.

由于索引仅用于加快在记录中搜索匹配字段的速度，因此，在执行插入或删除操作时，仅用于输出的索引字段只会浪费磁盘空间和处理时间，因此应该避免.考虑到二进制搜索的性质，数据的基数或唯一性也很重要.对基数为2的字段进行索引将把数据一分为二，而基数为1000的字段将返回大约1000条记录.使用如此低的基数，有效性将降低为线性排序，如果基数小于记录数的30%，查询优化器将避免使用索引，从而有效地使索引浪费空间.