一. InnoDB 索引
InnoDB 支持以下几种索引:
B + 树索引
全文索引
哈希索引
本文将着重介绍 B + 树索引. 其他两个全文索引和哈希索引只是做简单介绍一笔带过.
哈希索引是自适应的, 也就是说这个不能人为干预在一张表生成哈希索引, InnoDB 会根据这张表的使用情况来自动生成.
全文索引是将存在数据库的整本书的任意内容信息查找出来的技术, InnoDB 从 1.2.x 版本支持. 每张表只能有一个全文检索的索引.
B + 树索引是传统意义上的索引, B + 树索引并不能根据键值找到具体的行数据, B + 树索引只能找到行数据锁在的页, 然后通过把页读到内存, 再在内存中查找到行数据. B + 树索引也是最常用的最为频繁使用的索引.
二. 什么是 B + 树
概念
B + 树是一种平衡查找树, 其实先想想看为什么要用平衡查找树, 不用二叉树? 普通的二叉树可能因为插入的数据最后变成一个很长的链表, 怎么能提高搜索的速度呢? 你可以想想, 为什么 HashMap 和 ConcurrentHashMap 在 JDK8 的时候, 当链表大于 8 的时候把链表转成红黑树(红黑树也是平衡查找树). 技术思维是想通的, 那么答案无非是加快速度, 性能咯.
一个 B + 树有以下特征:
有 n 个子树的中间节点包含 n 个元素, 每个元素不保存数据, 只用来索引, 所有数据都保存在叶子节点.
所有叶子节点包含元素的信息以及指向记录的指针, 且叶子节点按关键字自小到大顺序链接.
所有的中间节点元素都同时存在于子节点, 在子节点元素中是最大 (或最小) 元素.
那么我们先来看一个 B + 树的图
所有的数据都在叶子节点, 且每一个叶子节点都带有指向下一个节点的指针, 形成了一个有序的链表. 为什么要有序呢? 其实是为了范围查询. 比如说 select * from Table where id> 1 and id <100; 当找到 1 后, 只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点, 极大提到了区间查询效率. 是不是范围查询的话 hash 就搞不定这个事情了? 以下为 B + 树的优势:
单一节点存储更多元素, 减少 IO
所有查询都要找到叶子节点, 查询稳定
所有叶子节点形成有序链表, 方便范围查询
一般性情况, 数据库的 B + 树的高度一般在 2~4 层, 这就是说找到某一键值的行记录最多需要 2 到 4 次逻辑 IO, 相当于 0.02 到 0.04s.
三. 聚集索引和辅助索引
聚集索引
聚集索引是按表的主键构造的 B + 树, 叶子节点存放的为整张表的行记录数据, 每张表只能有一个聚集索引. 优化器更倾向采用聚集索引. 因为直接就能获取行数据.
请选择自增 id 来做主键, 不要非空 UK 列. 避免大量分页碎片. 下面来看一个聚集索引的图:
那么很简单了, 每个叶子节点, 都存有完整的行记录. 对于主键的查找速度那是相当的快, 美滋滋.
辅助索引
辅助索引也叫非聚集索引, 叶子节点除了键值以外还包含了一个 bookmark, 用来告诉 InnoDB 在哪里可以找到对应的行数据, InnoDB 的辅助索引的 bookmark 就是相对应行数据的聚集索引键. 也就是先获取指向主键索引的主键, 然后通过主键索引来找到一个完整的行. 如果辅助索引的树和聚集索引的树的高度都是 3, 如果不是走主键索引走辅助索引的话, 那么需要 6 次逻辑 IO 访问得到最终的数据页. 辅助索引和聚集索引的概念关系图如下:
四. 索引实战
设计索引
设计索引的时候, 无论是组合索引还是普通索引等. 一般经验是, 选择经常被用来过滤记录的字段, 高选择性, 高区分性. 别把性别字段设计索引, 性别属于低选择性的. 你可以选择名字嘛, 你好我大名叫苗嘉杏:)
知道加索引快, 但是也别乱加索引, 插入以及更新索引的操作 InnoDB 都会维护 B + 树的, 多加很多索引只会导致效率降低!
不要用重复的索引, 比如有个联合索引是 a,b, 你又整个 a 列的普通索引. 那不是搞事么?
不要在索引上用函数和 like
一颗聚集索引 B + 树可以放多少行数据?
这里我们先假设 B + 树高为 2, 即存在一个根节点和若干个叶子节点, 那么这棵 B + 树的存放总记录数为: 根节点指针数 * 单个叶子节点记录行数. 假设一行记录的数据大小为 1k, 那么单个叶子节点 (页) 中的记录数 = 16K/1K=16.
那么现在我们需要计算出非叶子节点能存放多少指针, 我们假设主键 ID 为 bigint 类型, 长度为 8 字节, 而指针大小在 InnoDB 源码中设置为 6 字节, 这样一共 14 字节, 我们一个页中能存放多少这样的单元, 其实就代表有多少指针, 即 16kb/14b=1170. 那么可以算出一棵高度为 2 的 B + 树, 大概能存放 1170*16=18720 条这样的数据记录.
根据同样的原理我们可以算出一个高度为 3 的 B + 树大概可以存放: 1170*1170*16=21902400 行数据. 所以在 InnoDB 中 B + 树高度一般为 1-3 层, 它就能满足千万级的数据存储. 在查找数据时一次页的查找代表一次 IO, 所以通过主键索引查询通常只需要 1-3 次逻辑 IO 操作即可查找到数据.
Cardinality 值
如何判断一个索引建立的是否好呢? 可以用 show index from 指令查看 Cardinality 值, 这个值是一个预估值, 而不是一个准确值. 每次对 Cardinality 值的统计都是随机取 8 个叶子节点得到的.
对于 innodb 来说, 达到以下 2 点就会重新计算 cardinality
如果表中 1/16 的数据发生变化
如果 stat_modified_counter>200 000 0000
实际应用中,(Cardinality / 行数)应该尽量接近 1. 如果非常小则要考虑是否需要此索引. 实战一下, 比如有一张表, 我们来 show index 一下
- MySQL> show index from Order;
- +---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
- | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
- +---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
- | Order | 0 | PRIMARY | 1 | id | A | 99552 | NULL | NULL | | BTREE | | |
- | Order | 1 | IDX_orderId | 1 | orderId | A | 96697 | NULL | NULL | | BTREE | | |
- | Order | 1 | IDX_productId | 1 | productId | A | 52 | NULL | NULL | | BTREE | | |
- +---------+------------+------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
- 3 rows in set (0.00 sec)
那么可以看到 IDX_productId 这个索引的 Cardinality 比较低.
需要强制刷新 Cardinality 值的话可以用:
analyze local table xxx;
参考:
MySQL5.1 参考手册 - http://dev.mysql.com/doc/refman/5.1/zh/index.html
《MySQL 技术内幕》
《小灰漫画》
https://www.cnblogs.com/leefreeman/p/8315844.html
来源: https://www.cnblogs.com/GrimMjx/p/10540263.html