<hr class=“my12大纲无baw0 bb bc-POWER-400”/
想改进此问题吗？编辑此帖子，更新问题，使其只关注一个问题。
两年前关闭
鉴于索引在数据集大小增加时非常重要，有人能解释一下索引是如何在数据库无关级别工作的吗
有关为字段编制索引的查询的信息，请查看如何为数据库列编制索引
为什么需要它？
当数据存储在基于磁盘的存储设备上时，它被存储为数据块。这些数据块全部被访问，使它们成为原子磁盘访问操作。磁盘块的结构与链表的结构非常相似；两者都包含一个数据节，一个指向下一个节点（或块）位置的指针，并且两者不需要连续存储
由于许多记录只能在一个字段上排序，因此我们可以声明，在未排序的字段上搜索需要线性搜索，这需要（N+1）/2块访问（平均），其中N是表跨越的块数。如果该字段是非键字段（即不包含唯一的条目）则必须在N块访问中搜索整个表空间
而对于排序字段，可以使用二进制搜索，它具有log2 N块访问。此外，由于数据是在给定非键字段的情况下排序的，因此一旦找到更高的值，就不需要搜索表的其余部分以寻找重复值。因此，性能显著提高
什么是索引？
索引是对多个字段上的多个记录进行排序的一种方法。在表中的一个字段上创建索引将创建另一个数据结构，该结构保存字段值以及指向该字段相关记录的指针。然后对该索引结构进行排序，允许对其执行二进制搜索
索引的缺点是，这些索引需要额外的磁盘空间，因为索引使用MyISAM引擎一起存储在一个表中，如果同一个表中的许多字段都被索引，则此文件可以快速达到基础文件系统的大小限制
它是如何工作的？
首先，让我们概述一个示例数据库表模式
磁盘上的字段名数据类型大小 id（主键）无符号整数4字节 firstName字符（50）50字节 lastName字符（50）50字节 emailAddress字符（100）100字节
注意：char被用来代替varchar，以便在磁盘上获得准确的大小值。
此示例数据库包含500万行，未编制索引。现在将分析几个查询的性能。这些查询是使用id（排序键字段）的查询和使用名字的查询（非关键字未排序字段）
示例1–排序字段与未排序字段
假设我们的样本数据库中有固定大小的r=5000000记录，记录长度为r=204字节，它们使用MyISAM引擎存储在一个表中，MyISAM引擎使用默认的块大小B=1024字节。该表的阻塞因子为bfr=（B/r）=1024/204=5个记录/磁盘块。保存该表所需的块总数为N=（r/bfr）=5000000/5=1000000个块
考虑到id字段是一个关键字段，对id字段的线性搜索需要平均N/2=500000块访问才能找到一个值。但是由于id字段也是经过排序的，因此可以进行二进制搜索，要求平均log2 1000000=19.93=20块访问。我们可以立即看到这是一个drast集成电路改进
现在，firstName字段既不是排序字段，也不是键字段，因此不可能进行二进制搜索，值也不是唯一的，因此表将需要搜索到底，以获得准确的N=1000000块访问。索引的目的就是纠正这种情况
由于索引记录只包含索引字段和指向原始记录的指针，因此它将比它所指向的多字段记录小。因此，索引本身需要的磁盘块比原始表少，因此需要的块访问次数更少。中firstName字段上的索引概述如下
磁盘上的字段名数据类型大小 firstName字符（50）50字节 （记录指针）特殊4字节
注意：MySQL中的指针长度为2、3、4或5字节，具体取决于表的大小
示例2–索引
假设我们的样本数据库为r=5000000记录，索引记录长度为r=54字节，并使用默认块大小B=1024字节。索引的阻塞因子为bfr=（B/r）=1024/54=18每个磁盘块记录。保存索引所需的块总数为N=（r/bfr）=5000000/18=277778块
现在，使用firstName字段的搜索可以利用索引来提高性能。这允许对索引进行二进制搜索，平均块访问次数为log2 277778=18.08=19。要查找实际记录的地址，需要进一步的块访问才能读取，从而使总数达到19+1=20 块访问，与在非索引表中查找firstName匹配项所需的1000000个块访问相差甚远
什么时候应该使用它？
鉴于创建索引需要额外的磁盘空间（上述示例中增加了277778个块，增加了约28%），并且过多的索引可能会导致文件系统大小限制引起的问题，因此必须仔细考虑选择要索引的正确字段
由于索引仅用于加快在记录中搜索匹配字段的速度，因此，在执行插入或删除操作时，仅用于输出的索引字段只会浪费磁盘空间和处理时间，因此应避免。此外，鉴于二进制搜索的性质，基数或数据的唯一性很重要。对基数为2的字段进行索引将把数据一分为二，而基数为1000的字段将返回大约1000条记录。基数如此低，效率将降低为线性排序，如果基数小于数据的30%，查询优化器将避免使用索引记录编号，有效地使索引浪费空间