本质
索引是排好序的数据结构,可以帮助MySQL高效获取数据。
索引的作用
考虑一张表设计和数据如上图,第一列是指数据行在磁盘的存放地址,
查询sql语句为
select *from t where t.Col2 = 89;
不用索引,需要从第一行开始遍历,查询每一行的Col2值是否等于89,需要查找6次。 而MySQL的数据是存放在磁盘的,每一行的查找相当于做了一次磁盘IO操作,磁盘的寻道时间大约为10ms,假如查找100次,就需要1s,效率非常低,更不用说成千上百万行记录的表。
给Col2加上索引,例如用上图的二叉树,树的节点是key,即Col2的值,value是索引所在行的磁盘文件地址(数据行在磁盘中存放不是连续的),那么从根节点查找Col2 = 89的值,只需要两次IO操作即可,比全表扫描快很多。
索引的优势
- 提高数据检索的效率,降低数据库的IO成本,类似于书的目录(每次翻页就是IO操作)。
- 通过索引列对数据进行排序,降低数据排序的成本,降低了CPU的消耗。
- 被索引的列会自动进行排序,包括【单列索引】和【组合索引】,只是组合索引的排序要复杂一些。
- 如果按照索引列的顺序进行排序,对应order by语句来说,效率就会提高很多。
索引的劣势:
- 索引会占据磁盘空间
- 索引虽然会提高查询效率,但是会降低更新表的效率。比如每次对表进行增删改操作,MySQL不仅要保存数据,还有保存或者更新对应的索引文件。
索引数据结构
- 二叉树
- 红黑树(平衡二叉树)
- 有序数组
- hash表
- B树
- B+树
为什么不用二叉树
考虑上图,对Col1进行索引,二叉树是长这样子
退化成了线性结构的链表,查询效率和全表扫描一样,复杂度是O(n)。
所以二叉树对于线性增长的字段是不适合做索引存储的。
为什么不用红黑树
对Col1进行索引,红黑树是长这样子
红黑树是采用二分法思维,除了具备二叉树的特点,最主要的特征是树的左右两个子树会自动平衡,在插入删除数据时通过左旋/右旋操作保持二叉树的平衡,不会出现左子树很高、右子树很矮的情况。
使用红黑树查找树查询的性能接近于二分查找法,查找时间复杂度是 O(log2n),是高效的数据结构。
存在问题:一张表动辄上千万的记录,即使红黑树具有自平衡功能,树也会很高,树高 = log2(记录数),
至少是20,假如元素落在叶子节点,就需要经历20次IO操作,还是有效率问题。
有序数组
对Col1进行索引,有序数组是长这样子
index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
value | 1 | 2 | 3 | 4 | 5 | 6 |
有序数组在等值查询和范围查询场景中的性能都非常优秀。
如果你要查 Col = 4,用二分法就可以快速得到,这个时间复杂度是 O(log(N))。
同时很显然,这个索引结构支持范围查询。
如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,成本太高。
所以,有序数组索引只适用于静态存储引擎,比如你要保存的是 2017 年某个城市的所有人口信息,这类不会再修改的数据。
hash表
考虑对表的名字列用hash做索引,如下图
image.png
Hash表,以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列,Value可以存储行记录或者行磁盘地址。每次插入数据,都对key用hash算法得出散列值,放入数组中。
当发生hash冲突时,采用开链表法解决,当链表太长会rehash,或者改用红黑树存储数据。
优点:
- 在等值查询时效率很高,时间复杂度为O(1),比B+树索引高效;
缺点:
- 仅满足等值查询,例如 "= ", "IN",不支持范围快速查找,范围查找时还是只能通过扫描全表方式;
- hash冲突问题。
所以,哈希表这种结构适用于只有等值查询的场景,比如 Redis,Memcache 及其他一些 NoSQL 引擎。
显然这种并不适合作为经常需要查找和范围查找的数据库索引使用。
B树
红黑树的缺点是大数据下树会变得很高,解决思路是横向扩展每层节点个数,每层存储更多的节点,就可以降低树的高度。 每个节点对应一块磁盘空间,分配更大的磁盘空间,以容纳更多的节点。
改造后的数据结构就是B树,每个大节点下可以存放多个数据。
B树特点:
- 叶节点具有相同的深度,叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
相比二叉平衡查找树,在整个查找过程中,虽然数据的比较次数并没有明显减少,但是磁盘IO次数会大大减少。同时,由于比较是在内存中进行的,比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景,所以使用B树构建索引可以很好的提升查询的效率。
B树缺点:
-
B树不支持范围查询的快速查找,想要查找15和49之间的数据,查找到15之后,需要回到根节点重新遍历查找,需要从根节点进行多次遍历,查询效率有待提高。
-
节点存储的是行记录,行的大小随着列数的增多,所占空间会变大。这时,一个页中可存储的数据量就会变少,树相应就会变高,磁盘IO次数就会变大。
B+树(多路平衡树)
MySQL实际上对B树再进行改造,得到B+树
B+树特点:
- 非叶子节点不存储数据,只存储索引(冗余),可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接,提高区间访问性能。
假如要查找值为30的行,数据查找过程如下:
- 先把根节点的索引全部load进内存,因为数据是已经有序的,可以使用二分查找,定位下一级索引位置。
- 定位到第二级索引后,也是load进内存,定位第三级索引。
- 定位到第三级索引,继续二分查找,找到索引位置,并取出索引对应的行数据。
过程只需要三次IO操作,约等于30ms。
假如要查找18 ~ 50的行,数据查找过程如下:
- 定位到value为18的索引,需要三次IO操作;
- 从18的索引开始,依次读取索引下一个索引,直到>50为止,再需要两次IO操作。
B树与B+树两个区别:
- B树:非叶子节点和叶子节点都会存储数据。
- B+树:只有叶子节点才会存储数据,非叶子节点只存储键值,所以B+树一个页能放入更多的索引,同样的数据量,树高更低。叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表,方便进行范围搜索。
MySql默认一个页的长度为16KB,即分配给B+树每个节点大小。
mysql> show global status like 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)
假如索引字段是BigInt,占8B,索引存储的值即磁盘地址长度占6B,加起来就是14B,页大小为16KB情况下,每页可以放 16KB / 14B = 1170个索引,假如叶节点,即存放数据的节点,每行数据大小为1KB,即每页可以放16个数据行,那么树高为3的B+树,可以放满 1170 * 1170 * 16 = 2000w个索引和数据,千万级别的数据依然很高。
而且MySQL底层,实际上会把所有非叶子结点放到内存中,因为非叶子节点内存占用少,例如树高为3的B+树,放满索引后,索引大小为 1170 * 1170 * 14B = 18.2MB,所以查找数据只需要1次IO操作,效率高。
网友评论