美文网首页mysql
MySQL - 索引本质、数据结构

MySQL - 索引本质、数据结构

作者: kyo1992 | 来源:发表于2021-04-13 08:59 被阅读0次

    本质

    索引是排好序的数据结构,可以帮助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的消耗。
    1. 被索引的列会自动进行排序,包括【单列索引】和【组合索引】,只是组合索引的排序要复杂一些。
    2. 如果按照索引列的顺序进行排序,对应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操作,效率高。

    相关文章

      网友评论

        本文标题:MySQL - 索引本质、数据结构

        本文链接:https://www.haomeiwen.com/subject/ywpwkltx.html