数据库索引的工作原理

技术背景

在基于磁盘的存储设备中，数据以数据块的形式存储，磁盘块的访问是原子操作。由于数据存储的特性，在未排序字段上搜索数据通常需要线性搜索，平均需要 (N + 1) / 2 次块访问（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

未索引字段的查询：对于 firstName 字段，由于它既未排序也不是键字段，进行精确查询时需要全表扫描，即需要访问 N 个块。
索引字段的查询：为 firstName 字段创建索引，索引记录结构如下：

1
2
3

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

此时，通过索引进行查询可以利用二分搜索，平均需要 log2 N 次块访问，再加上一次块访问来读取实际记录的地址，总块访问次数远低于未索引表的查询。

核心代码

创建索引的 SQL 语句

1 2	`CREATE INDEX name_index ON User (Name);`

最佳实践

选择合适的字段进行索引：索引会占用额外的磁盘空间，并且过多的索引可能会导致文件系统大小限制问题。因此，应仅对经常用于查询条件的字段创建索引，避免对仅用于输出的字段创建索引。
考虑数据的基数：数据的基数或唯一性对于索引的有效性很重要。如果字段的基数较低，索引的效果可能会降低到线性排序，查询优化器可能会避免使用该索引。
区分聚集索引和非聚集索引：在不同的场景下，聚集索引和非聚集索引有不同的优势，需要根据具体情况进行选择。