索引通过B+树等有序结构减少数据扫描量，将查找时间复杂度从O(n)降为O(log n)，支持快速等值、范围查询及排序分组，显著提升查询效率。
数据库索引能极大加快查询速度，核心在于它改变了数据的访问方式，避免了效率低下的全表扫描。你可以把索引想象成一本书的目录，通过目录能快速翻到目标页码，而不用一页一页地去翻找。
减少需要扫描的数据量
没有索引时，数据库查找某条记录只能从头到尾一行一行地检查，这叫全表扫描，数据越多越慢。索引通过建立一个精简的、有序的数据结构（如B+树），只包含被索引列的值和对应数据的物理位置。当执行查询时，数据库引擎先在体积小得多的索引中查找，迅速锁定目标数据所在的磁盘块或数据页，然后直接去那里读取完整记录。
- 全表扫描时间复杂度是 O(n)，数据量翻倍，最坏情况查找时间也翻倍
- B+树索引查找时间复杂度是 O(log n)，即使数据量激增，查找所需的步骤增长也非常缓慢
利用高效的数据结构实现快速定位
最常见的索引结构是B+树，它是一种多路平衡搜索树，特别适合磁盘存储环境。
- 分层结构：B+树有多个层级，根节点在上，叶子节点在下。内部节点存放索引键值用于导航，所有实际数据行的指针都集中在叶子节点
- 矮胖设计：每个节点可以存储大量索引项（比如上千个），使得树的高度非常低。对于亿级数据，B+树通常只有3-4层
- 快速查找：查找一条记录，只需从根节点开始，逐层比较，经过3-4次磁盘I/O就能定位到叶子节点中的目标数据位置，相比全表扫描可能需要数百万次I/O，效率提升巨大
优化特定类型的查询操作
索引不仅加速等值查询，对范围查询、排序和分组也有显著效果。
- 范围查询：由于B+树的叶子节点用双向链表连接，并且键值是有序的，查找“日期在2025年1月1日到2月1日之间”的记录时，数据库能快速定位到起始点，然后顺序扫描后续相关节点，跳过所有无关数据
- 排序与分组：如果查询要求按某个索引列排序（ORDER BY）或分组（GROUP BY），数据库可以直接利用索引中已有的有序数据，省去了额外的排序操作，大大节省CPU和内存资源
- 覆盖索引：如果查询用到的所有字段都包含在某个索引中，数据库甚至不需要回到主表去查找数据，直接从索引里就能拿到结果，这种称为“覆盖索引”，性能最佳
