基本翻译自 How does database indexing work?
本文适用于 MongoDB、MySQL 等多种使用 B-tree 作为索引数据结构的数据库。
为什么需要索引？
当数据储存到基于磁盘的储存设备上时，数据被储存为数据块。磁盘块的结构与链表一样；都是一部分包含数据，一个指针指向下一个块，并且这两者不一定要连续储存。
由于这些记录只在一个字段上排序，我们可以说搜索非排序字段需要线性搜索，这平均需要访问 N/2 个块，N 是数据表对应的磁盘块总数目。如果那个字段是一个 no-key 字段（比如不包含唯一约束），那么整个表的空间 N 都需要被搜索到。
然而对于有序字段，可以使用二分搜索，这只需要访问 log2 N。
索引是什么？
索引是一种根据多个字段排序记录的方式。创建一个基于表中一个字段的索引会创建一个包含字段值和指向记录对应的磁盘块的指针的数据结构。这个索引结构然后被排序，使二分搜索可以作用在这上面。
索引的负面是这些索引需要额外的磁盘空间。
索引如何工作？
假设一个数据表结构：
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这个数据表含有 5000000 行并且没有被索引。
有序 vs 无序字段
假定有 r = 5000000 个记录，每个记录的大小是 R = 204 bytes，默认的 MyISAM 引擎的默认块的大小是 B = 1024 bytes。则表的块因数是 bfr = (B/R) = 1024/204 = 5 个记录，每个磁盘块。整个数据表对应的总块数是 N = (r/bfr) = 5000000/5 = 1,000,000。
由于 id 字段是一个 key field，所以线性搜索 id 字段平均需要访问 N/2 = 500,000 个块。但因为 id 字段也是有序的，使用二分搜索后平均需要访问 log2 1000000 = 19.93 = 20 个块。我们可以看出这是一个很大的提升。
由于 firstName 既不是有序的也不是 key field，所以需要扫描整个表，块数为 N = 1,000,000。
由于索引记录只包含被索引的字段和一个指向磁盘块的指针，所以索引记录会比它指向的多个字段的记录更小。所以相比原始数据表索引需要更少的磁盘块，因此只需要更少的磁盘块。基于 firstName 字段的索引结构：
Field name Data type Size on disk
firstName Char(50) 50 bytes
(record pointer) Special 4 bytes索引
由于数据表有 r = 5,000,000 条记录和一个大小为 R = 54 bytes 使用 B = 1,024 bytes 的索引记录。索引的块因数为 bfr = (B/R) = 1024/54 = 18 条记录每个磁盘块。索引对应 N = (r/bfr) = 5000000/18 = 277,778 块。
现在可以使用索引来提高用到 firstName 字段搜索的性能。对索引使用二分搜索后平均需要访问 log2 277778 = 18.08 = 19 块。为了找到真实记录对应的地址，需要多读取一个块，所以总数是 19 + 1 = 20，与未建索引前的 1,000,000 相比是很惊人的。
什么时候使用？
由于创建索引
- 需要消耗额外的磁盘空间（上面是额外增加了 277,778 个块，约 28% 的增长 ），
- 太多索引会造成文件系统大小限制的问题
- 插入和删除数据后要操作索引
所以建立索引前需要慎重考虑。
数据的基数也很重要。索引的大小为 数据总大小 / 基数。索引越大，消耗的磁盘空间越大。低基数会使效率退化为线性排序，并且查询器会避免使用小于 30% 记录数的基数，所以低基数索引纯粹是浪费空间
复合索引
复合索引可以被看做一个包含多个索引字段值的有序的列表。 -- 来自 Multiple-Column Indexes
只有复合索引的最左索引部分可以使用索引。比如你有一个 3 列索引 (col1, col2, col3)，你只可以使用 (col1), (col1, col2), 和 (col1, col2, col3)。原因是在 B-tree 搜索[2]中，是通过比较大小来进行搜索，而在复合索引中， 大小由最左索引部分决定，比如 (10, , ) > (9, , )、(10, 9, 8) > (9, 100, 100)。