数据库索引的底层原理：B+树是怎么让查询变快的

面试必问、工作中常用，但很多人只知道"加索引能加速查询"，不知道为什么。搞懂原理才能避免乱加索引反而拖慢写入。

没有索引会怎样

没有索引的表就像一本没有目录的字典。查一个字，只能从第一页开始一页页翻，直到找到为止。这叫全表扫描，数据量大的时候慢得离谱。100万行数据查一条，最坏情况要扫描100万次。

B+树：索引的数据结构

MySQL的InnoDB引擎默认用B+树做索引。B+树的特点：所有数据都存在叶子节点，叶子节点之间用双向链表连接，非叶子节点只存索引键值用于导航。一棵三层的B+树大约能存2000万行数据，也就是说查任何一条记录最多只需要3次磁盘IO。这就是索引快的根本原因——把O(n)的线性查找变成了O(log n)的树查找。

聚簇索引和二级索引

InnoDB的主键索引叫聚簇索引，叶子节点直接存了整行数据。二级索引（非主键索引）的叶子节点存的是主键值，查到主键后还要再回表查聚簇索引拿到完整数据。这就是为什么有时候走了索引还是要查两次。覆盖索引可以避免回表——如果查询的字段都在索引里，直接从索引返回结果，不用再查主键索引。

索引不是万能的

索引能加速读，但会拖慢写。每次INSERT、UPDATE、DELETE都要同时更新索引树。一张表上六七个索引，写入性能可能下降一半以上。所以索引要精不要多，只给真正频繁查询的字段加。另外，索引对模糊查询"like '%xxx'"无效，对函数作用后的字段也无效（除非用函数索引）。

联合索引和最左匹配

联合索引(a, b, c)的B+树先按a排序，a相同再按b排序，b相同再按c排序。所以查询条件必须包含a才能用到这个索引，这就是最左匹配原则。WHERE a=1 AND b=2能用，WHERE b=2 AND c=3不能用（跳过了a）。WHERE a=1 AND c=3只能用到a这部分，c用不上。理解这个原则，才能设计出真正有效的联合索引。