数据库索引

1 索引的数据结构

MySQL的底层存储引擎支持 InnoDB 和 MyISAM 两种，而默认存储引擎 InnoDB 采用的是B+树来作为索引的存储结构。

那么为什么 InnoDB 存储引擎会使用 B+ 树来存储数据 ，而不是采用 B- 树、红黑树 或是 AVL 树 来存储索引？

2 数据结构的比较

MySQL需要把数据持久化到磁盘上，因此需要频繁地读取磁盘上的数据，因此磁盘 IO 的次数很大程度上决定了查询效率，磁盘 IO 每次以页为单位进行。

对于大规模数据的索引来讲，红黑树和 AVL 的结构往往会导致 深度过大 而造成磁盘 IO 次数增多导致效率低下。同时为了保证平衡会进行频繁的结构调整。而B-树和B+树的特点是每一个层的节点数量更多，树的层数更小，这样查询的时候就能够减少磁盘 IO 的次数。

另外B-树的非叶子节点都存有数据域，这无疑增加了非叶子节点的大小，而减少了每一磁盘页中所能容纳的节点数量；而B+树只有叶子结点来存储数据，节点更小，从而磁盘页能够存储更多的节点，磁盘 IO 次数更少。

除此之外，深入分析数据库索引和底层的存储结构能发现B-树和B+树更重要的区别。

3 数据库存储结构

① B-树

对于 InnoDB 来说，所有的数据都是以键值对（key-data）的方式存储的，主键索引和辅助索引在存储数据时会将 id 和 index 作为键，将所有列和 id 作为键对应的值。这个key就是存储在B+树非叶子节点中的值。在B-树中除了键外，还会存储data值。

再提一次这句话： B-树可以在非叶结点中存储数据，但是 B+ 树的所有数据其实都存储在叶子节点中。

在B-树中，由于所有的节点都可能包含目标数据，我们总是要不止一次地从根节点向下遍历子树查找满足条件的数据行，这个特点带来了大量的随机 IO，也是 B-树最大的性能问题。

如上：如果我要查找【位于4到16之间的所有值】的时候，就需要：

加载 node1 所在的页
找到指向 node2 的指针，并加载所在页，遍历页面中的数据，发现还没找全；
再一次加载 node1 所在的页，发现还没找全；
找到指向 node3 的指针，并加载所在也，遍历页面中的数据，完成查找。

这样一来，如果范围查询需要跨越不同的节点，都需要从根节点向下遍历所有子节点来查找。会经历多次磁盘 IO。

② B+ 树

而使用 B+树，所有的节点都储存在叶子节点中，此外通过构建树的过程中，还可以保证每一个叶子节点中的数据都是有序（按照键值排序）的，所以我们还可以在叶子节点中增加一个（双向）的指针，来指向相邻节点。如图中每个灰色节点都代表磁盘上存储数据的一个页。这样当出现跨页的时候，就不需要从根节点从上至下查找了，只需要根据指针找到下一页。

此外也可以发现，由于 B+ 树中所有的数据都连在叶子节点上，那么对于所有的查询来讲，其查询时间即查询层数都是相等的，比较稳定。B+ 树是数据库底层的真实数据存储结构。

③ 聚簇索引与非聚簇索引

聚簇索引

在数据库中，我们可能会根据需要建立多个不同用途的索引，每个索引都是组成像上述B+树的结构，但是实际上在硬盘中只会存储一份数据文件。像上述图中这样把索引与数据建在一起的索引称为聚簇索引。

聚簇索引默认建立在数据表的主键上。

非聚簇索引

当再建立新的索引时，就不需要存储data文件了，而是只需要存储索引结构，这种索引与数据分离的就成为 非聚簇索引 。这时候每个叶子结点存储的不是 data 而是指向聚簇索引的 key值，通过 key 值再反过来查找聚簇索引。也就是需要二次查找。

覆盖索引

当一个语句检索的列只包含建立非聚簇索引的列及主键，这样在非聚簇索引的结构中就包含了我们需要的全部数据项，不用再去二次查找聚簇索引了。

最左匹配原则

在建立联合索引时，如 (a,b,c)上建立索引，会先对 a 进行排序，在此基础上对 b排序，最后是 c。因此 a 是有序的，而 b 和c 无序。简单理解的话，假设a,b,c的取值范围都是 0~9 那么在建立索引的时候就是把 a放在百位，把b放在十位，把c放在个位，再对这些数字排序。

联合索引在检索数据是，会从索引的最左边开始匹配，直到匹配到 where 子句中一个无法使用索引的条件。

所以单独对a进行检索，可以使用上述索引abc，但是对b,c单独检索，则无法使用。索引的匹配一定是与索引建立时候的顺序是一致的。

此外，对 a,c 进行检索，则只能对 a使用索引，而c则不能。

（这里不考虑无法使用索引的条件，只是说明匹配原则。）

④ B树与B+树的对比

B 树只适合随机检索， B+ 树同时支持随机检索和顺序检索。
B+ 树节点的利用效率更高，可减少 IO 次数，磁盘读写代价更低。
B+ 树的查询效率更加稳定。B 树的查询过程可能在非叶子节点结束；B+ 树的查询全部在叶子节点结束。
B 树在提高 IO 性能的同时并没有解决元素遍历效率低下的问题。进行范围查询，当元素存储在不同的磁盘页上时，需多次从根节点开始查找；而 B+ 树的叶子节点使用双指针连接在一起，且是有序的，只要遍历叶子结点就能实现整棵树的遍历。

4. 索引失效的情况

在一定条件下，索引可能会失效，即无法通过索引来加速查询过程。

where 子句中进行 NULL 判断
where 子句中使用 !=, <>, not 这样的判断
避免在 where 子句中使用 or，如果其中一个字段没有索引的话，将放弃使用索引
避免在 where 子句中使用 in
避免在 where 子句中=的左边使用表达式操作或者函数操作
避免在 where 子句中使用 ‘like’ 模糊查询
联合索引的最左原则

5. MyISAM 与 InnoDB 的索引的区别

MyISAM

主键索引：MyISAM 引擎使用B+树作为主键索引结果，叶节点的data域存放的是数据记录的地址。
辅助索引：MyISAM 的辅助索引在结构上跟主键索引没有什么区别，只是辅助索引的 key 可以重复，同样节点的data 域存放数据记录的地址。

InnoDB

主键索引： InnoDB 表数据文件本身就是一个索引结构，树的叶节点data域保存了完整的数据记录，即主键索引是聚集索引。
辅助索引： InnoDB 的所有辅助索引也构成一个B+ 树来存放，叶节点的data域存放的是数据记录的主键。即辅助索引需要通过这个主键再去二次检索主键索引。

6. 数据库存储引擎的对比

事务支持： InnoDB 支持事务，MyISAM 不支持事务。
外键支持： InnoDB 支持外键，而 MyISAM 不支持。
索引支持： InnoDB 是聚集索引，MyISAM 是非聚集索引。
锁支持： InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。
恢复：系统崩溃后，MyISAM恢复起来更困难。
InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快。
innoDB所有的表在磁盘上保存在一个文件中；myISAM存储成三个文件。

6.1 如何选择

如果要支持事务，选择 InnoDB。
如果大多是只是读查询，可以考虑MyISAM。如果既有读写也挺频繁，请使用InnoDB。

7. 索引的设计原则

符合最左前缀原则。联合索引时候，MySQL会匹配所有的等式条件直到第一个范围查询（>, <, between, like）这些就停止匹配。
更新频繁的字段不适合创建索引
较为频繁被查询的字段才适合创建索引
对于查询中很少涉及到的列，重复值较多的不要建立索引
不能有效区分数据的列不适合建立索引（如性别）
尽量地扩展索引，而不是新建索引
定义外键的数据列一定要创建索引
适合索引的列是出现在 where 子句的列，或者是连接子句中指定的列
使用短索引，如果对长字符串建立索引，应该指定一个前缀长度，这样能节省索引空间。
不要过度索引。索引需要占用存储空间。此外增删改操作都需要重新更新索引，会带来额外的时间消耗。

8. 其他小问题

为什么主键通常建议使用自增id

聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。

如果主键不是自增id，在不断地插入数据的过程中主键值是完全随机的，就需要不断地调整数据的物理地址、分页。而使用自增id作为主键，可以保证，相邻插入的数据一定保存在磁盘中相邻的位置，避免聚集索引的不断调整。

默认聚簇索引

聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引。

聚簇索引的劣势

维护索引很昂贵，特别是插入新行或者主键被更新导至要分页 (page split) 的时候。如果使用UUId（随机ID）作为主键，使数据存储稀疏，这就会出现聚簇索引有可能有比全表扫面更慢，所以建议使用int类型的auto_increment作为主键。

索引的优缺点

优点：加快查询速度
降低增删改速度，存储索引需要占用额外的空间。
每当数据库中有记录插入或删除时，索引都需要更新。如果有记录更新，任何搜索码属性受影响的索引也必须更新。

参考链接