数据库索引

复习定位

索引是通过对一列或多列的值进行排序来加快数据检索的一种数据结构。没有索引——数据库必须做全表扫描——遍历所有行来查找目标。索引的原理和书的目录一样——"索引"通过有序的键值和对应的页(行)地址——将需要扫描的行数从O(n)降低到O(log n)。但索引不是免费的——它占用额外的存储空间——增/删/改操作需要更新索引——因此索引越多写入越慢。

B+树索引的结构与原理

B+树是多路平衡搜索树——与B树的区别在于内部节点只存储键值(不存储数据指针)——叶子节点存储所有键值和对应的主键值(对于非聚簇)或完整行数据(B+树在InnoDB的聚簇索引实现中叶子节点包含行数据)。叶子节点之间通过双向链表连接——支持高效的范围扫描。

查找一个特定值的过程(以3层B+树、数百万行数据为例)：

1. 根节点(通常在内存缓冲池中)——在根节点的键数组中进行二分查找——确定应该进入哪个子节点(下层)。
2. 中间层节点(如果查询目标在中间范围内)——再次二分查找——定位到下一层的子节点。
3. 叶子节点——在叶子节点的键数组中二分查找定位到目标键——获取对应的行指针(非聚簇)或直接获取完整的行数据(聚簇索引)。因为叶子节点已按序排列且通过链表相连——一旦定位到起始位置——范围查询可以直接向后扫描链表直到结束。

B+树的最大优势是"高扇出"——每个节点可以包含数百到数千个键(取决于页大小和键大小)——使得绝大多数B+树的高度在2_{4层之间。一千万行数据的表——查找任意行只需2}3次磁盘I/O(因为根节点常驻内存缓冲池)。作为对比——如果直接用二分查找有序数组(不支持快速插入)——或二叉树(深度为O(log₂n)——对于千万条记录的树高约24层——需要24次I/O——不可接受)。

聚簇索引与非聚簇索引

聚簇索引(Clustered Index)——数据行的物理顺序与索引的键顺序相同——一张表最多只能有一个聚簇索引(因为数据只能按一种顺序物理排列)。InnoDB的主键强制作为聚簇索引——如果建表时没有显式定义主键——InnoDB会选择一个唯一的非空列作为主键——如果也不存在——则隐式创建6字节的ROWID作为主键。聚簇索引的叶子节点直接包含整行数据——所以主键查询只需一次B+树定位即可获取完整行——无需回表。

非聚簇索引(Secondary Index)——索引顺序与数据的物理排列无关——叶子节点存储的是索引键+主键值。查询非索引列时(即SELECT *或SELECT非索引列)——在非聚簇索引中找到匹配的主键值后——还需要回到聚簇索引再查一次才能获取完整行——这个过程称为"回表"。回表增加了额外的I/O次数——所以尽量使用覆盖索引(索引中已经包含查询需要的所有列)来避免回表。

覆盖索引——如果查询只需要使用索引中的列——而不需要访问其他列——InnoDB可以直接从非聚簇索引的叶子节点中获取数据而不需要回表——EXPLAIN输出的Extra列会显示"Using index"。

联合索引和最左前缀

联合索引(复合索引)是指在多个列上建立的索引——如INDEX(a,b,c)。索引中的行先按a排序——a相同时按b排序——b相同时按c排序。这使得索引在执行以下查询时有效：

• WHERE a=1——可用索引——因为a是前缀。
• WHERE a=1 AND b=2——可用索引——用到a和b
• WHERE a=1 AND b=2 AND c=3——完全用到三段索引
• WHERE a=1 AND c=3——只用到a列——b列被跳过——c条件无法使用索引排序(但可以通过a条件将范围缩小后再过滤c)
• WHERE b=2——完全不能使用这个联合索引——因为未从最左列a开始匹配

索引的代价与维护

索引不是免费的——每个索引在INSERT/UPDATE/DELETE时需要维护——数据变动时需要同步更新索引。如果一张表有多个索引——每次写入操作将变得昂贵(同时更新B+树的多个索引)。因此——索引的设计需要在查询性能和写入性能之间权衡。

复习检查

1. 为什么B+树的"高扇出"特性使得它比二叉树更适合数据库索引——相同数据量下B+树的高度比二叉树矮很多(约4~5层vs动辄20+层)——因此磁盘I/O次数更少。

2. 聚簇索引和非聚簇索引的叶子节点各自存储什么内容——聚簇索引存完整行数据——非聚簇索引存主键值——因此非聚簇索引查询非索引列时需要回表。

3. 联合索引INDEX(a,b,c)——对于WHERE a>5 AND b=3——索引能用到哪些列——a列的范围条件可以用到索引——但b列的等值条件不会在a被范围破坏后还用上排序——因此只有a能用索引过滤b=3因为a的扫出结果已经不是有序对b。

4. 什么是回表(Bookmark Lookup)——为什么覆盖索引可以避免回表——回表是指先从非聚簇索引找到主键值——再用主键到聚簇索引查完整行——覆盖索引所需的数据已全部包含在索引列和主键中——无需回表。

5. 一张表的索引越多越好吗——不是——每个索引占用存储空间——且每次数据更新都需要维护所有索引——对写入性能的影响日趋明显。

B+树的分裂与合并过程

当向B+树插入一个新键时——如果目标叶子节点已经满了(键的数量等于最大容量)——需要进行分裂(Split)操作。

分裂步骤：

1. 在叶子节点中将所有键(包括新键)排序——取中位数键。
2. 中位数键及其右侧的键被移动到新创建的叶子节点中——左侧的键保留在原节点中。
3. 中位数键的副本被提升到父节点中——父节点获取一个新的子指针指向新节点。
4. 如果父节点现在也满了——继续向上一层分裂——这种级联向上传播直到根节点也可能分裂——树的高度增加一层。

合并操作发生在删除操作之后——当叶子节点中的键数量低于某个阈值(通常是最大容量的一半)——尝试从相邻兄弟节点"借"键(Borrow)或与兄弟节点合并(Merge)。合并操作同样可能引起父节点键数下降——向上传播。B+树的自平衡特性正是通过分裂与合并机制来维护的——确保所有叶子的深度相同。

不使用索引的全表扫描

当数据库优化器评估一个查询的执行计划时——它会根据查询条件、可用索引、统计信息等估算各个计划的成本。在一些情况下——即使存在索引——优化器也可能选择全表扫描而不是使用索引：

• 返回行占比高——如果查询预计返回超过20-30%的行数——全表扫描(顺序读取)可能比索引扫描+大量回表(UPS随机读取)更快。
• 表很小——如果表只有几百行——全表扫描的I/O次数本来就很少——索引带来的额外查找开销可能超过顺序扫描。
• 索引列的选择性低——如性别列只有"男"、"女"两个值——通过索引找到50%的行再回表——比直接全表扫描慢得多(因为大量的随机I/O+每次回表vs顺序I/O全表扫描)。

MySQL的InnoDB与MyISAM的索引差异

InnoDB的索引是聚簇的——主键索引的叶子节点存放行数据。MyISAM的索引是非聚簇的——叶子节点存储指向行数据的指针(物理位移)。因为MyISAM不支持事务和行级锁——在MySQL 8.0+中InnoDB已成为默认存储引擎。

复习检查（续）

6. B+树索引的内部节点和叶子节点在存储内容上有什么区别——内部节点只存键值和子指针——叶子节点存键值和数据。

7. 联合索引的最左前缀匹配——INDEX(a,b,c)——在WHERE a=5 ORDER BY c条件下索引的使用情况——a用于过滤——c不能使用索引排序(因为a和c之间缺了b)。

8. 什么情况下优化器会放弃使用索引而选择全表扫描——查询预计返回大部分行、表太小、索引选择性太低(如性别列)——全表扫描比索引+回表便宜。

9. 覆盖索引为什么能在EXPLAIN的Extra列中显示"Using index"而不显示"Using index condition"——因为查询所需的所有列都已经存在于索引的定义列中——不需要回表访问数据行。

10. 索引维护的代价——INSERT时需要在各个索引的B+树中插入新键——可能引发节点分裂——UPDATE时如果更新了索引列的值——等于在索引中删除旧键和插入新键——写入密集的场景下索引数量越多性能下降越明显。

索引的命名规则与查看

MySQL中查看表的索引——SHOW INDEX FROM table_name——输出包括：Table(表名)、Non_unique(是否非唯一索引)、Key_name(索引名称)、Seq_in_index(该列在联合索引中的位置——从1开始)、Column_name(列名)、Cardinality(索引列的区分度——越大越好——反映不同值的数量)、Index_type(索引类型——BTREE/HASH/FULLTEXT)。

SHOW INDEX中Cardinality字段反映了索引列的不同值的数量——优化器根据Cardinality判断索引的选择性——选择性高(接近行数)表示索引能有效过滤——选择性低(如性别列只有两个不同值)则优化器可能放弃索引。统计信息不是实时的——由后台线程定期更新——通过ANALYZE TABLE table_name手动更新。

索引设计的基本原则

1. 为频繁出现在WHERE条件中的列创建索引
2. 为JOIN连接中使用的外键列创建索引
3. 为ORDER BY和GROUP BY中涉及的列创建索引——避免文件排序
4. 不要在选择性低的列(如性别、状态位)上创建单列索引
5. 创建联合索引时——选择性高的列放在最左侧
6. 避免创建过多索引——权衡查询加速和写入开销
7. 使用覆盖索引(将SELECT的列包含在索引中)避免回表
8. 对长字符串列使用前缀索引(只索引前N个字符)减少索引体积

这些原则不是绝对规则——需要根据实际的查询模式和数据分布通过EXPLAIN反复调优。

使用EXPLAIN分析索引使用

EXPLAIN SELECT * FROM orders WHERE user_id=100;的输出关键列：

• type——ref(使用非唯一索引的等值查找) > range(范围查找) > index(全索引扫描) > ALL(全表扫描)
• possible_keys——查询可用的索引
• key——实际使用的索引
• rows——估算的扫描行数(越小越好)
• Extra——"Using index"(覆盖索引) "Using where"(使用条件过滤) "Using filesort"(需要额外的排序操作——没有用到索引排序)

如果看到type=ALL——表示全表扫描——对于大表通常需要优化。如果Extra显示"Using filesort"——表示排序不能利用索引——可以考虑添加适当的索引来避免文件排序。

复习检查（续二）

11. MyISAM和InnoDB的索引最大区别——MyISAM非聚簇——叶子节点存储数据文件偏移指针——InnoDB聚簇——主键叶子节点直接存储完整的行数据。

12. 索引设计的一般原则——为WHERE和JOIN列创建索引——选择性高的列优先——避免低选择性列单列索引——少量索引优于过多索引。

13. EXPLAIN中type=ref和type=ALL的区别——ref表示使用非唯一索引的行匹配——ALL表示全表扫描——ref比ALL快得多。

14. 为什么长字符串列推荐前缀索引——索引占用的空间缩小——每个节点可容纳更多键值——使B+树扇出更大——树高更小——但前缀索引不能用于覆盖索引。

15. 索引的Cardinality(区分度)如何影响优化器——Cardinality接近行数表示索引选择性高——优化器更愿意使用该索引——Cardinality远小于行数(如性别)——优化器可能认为索引无助于加速查询。

哈希索引

哈希索引基于哈希表实现——对索引列的值进行哈希运算得到槽位指针。哈希索引只支持等值匹配(=、IN、<=>)——不支持范围查询(>、<、BETWEEN)和排序(ORDER BY)。因为哈希后值被随机化——不保留原始值的顺序关系。MySQL的Memory引擎显式支持哈希索引——InnoDB在运行时维护自适应哈希索引(AHI)——在频繁访问的索引页(由B+树管理)上自动建立等值查找的哈希优化——对应用层透明。

全文索引

全文索引用于对文本内容进行高效的关键词/短语搜索——MySQL的InnoDB和MyISAM支持FULLTEXT索引——底层使用倒排索引(inverted index)结构——记录每个单词出现在哪些文档(行)中。MATCH(column) AGAINST('keyword')语法使用全文索引——替代LIKE '%keyword%'的低效全表扫描。全文索引适用于文章内容搜索、日志分析等场景。

空间索引

MySQL MyISAM和InnoDB支持空间数据类型(GEOGRAPHY/GEOMETRY)——通过R-Tree索引进行高效的邻近查询和范围查询。常用于地理信息系统(GIS)和LBS应用——如"查询附近500米的店铺"。在MySQL 8.0+中——InnoDB开始原生支持空间索引。

联合索引的排序优化

联合索引不仅可以加速WHERE过滤——还可以加速ORDER BY排序。例如——INDEX(city, age)可以同时满足WHERE city='Beijing' ORDER BY age的过滤和排序需求——因为索引先按city排序——city相同的数据行按age排序——在city被限定后——age已经是有序的——无需额外的文件排序(filesort)操作。

如果排序方向不一致——ORDER BY city ASC, age DESC——索引默认是升序的——age的降序排序无法利用索引有序性——可能需要文件排序。MySQL 8.0开始支持降序索引——INDEX on city ASC, age DESC——可以正确处理混合排序方向。

复习检查（续三）

16. 哈希索引和B+树索引的适用场景差异——哈希索引只支持等值查找——B+树索引支持范围查找和排序。

17. 全文索引的底层结构——倒排索引——记录关键字到文档ID的映射关系——支持高效的全文搜索。

18. 联合索引INDEX(city, age)——对于WHERE city='Beijing' ORDER BY age——为什么不需要额外排序——因为city相同时age已经按索引顺序有序。

19. 空间索引的数据结构和应用——使用R-Tree结构——用于地理位置的最近邻查询。

20. MySQL 8.0的降序索引特性——INDEX ON col1 ASC, col2 DESC——允许索引在ORDER BY时同时处理升序和降序——避免文件排序。