请选择 进入手机版 | 继续访问电脑版

热点推荐

查看: 14|回复: 0

MySQL-索引

[复制链接]
  • TA的每日心情
    开心
    昨天 09:36
  • 签到天数: 256 天

    [LV.8]以坛为家I

    2万

    主题

    2万

    帖子

    8万

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    85108
    发表于 3 天前 | 显示全部楼层 |阅读模式
    索引的作用

    索引有点像目录,目录就是为了提高查找效率的。数据库中存储着成千上万条数据,如果没有索引,查找数据会变得很漫长,所以索引的作用就是为了提高数据的查找效率的。
    索引的模型分类

    一般来说,索引有三种数据结构模型:

    • hash模型
    • 有序数组
    • 树模型
    hash模型

    可以联想java中的HashMap,底层是一个数组,key通过hash得到数组中的一个位置,把value存储到对应的位置上,如果出现不同的key对应的相同的位置,会拉出一个链表。

    • 等值查询:平均时间复杂度O(1)
    • 范围查询:平均时间复杂度O(N)
    • 维护成本:插入,如果使用头插法:O(1)/删除,可能遍历链表,O(N)
    有序数组

    有序数组,所有的数据会按照某个字段进行排序。

    • 等值查询:二分法,平均时间复杂度O(log(N))
    • 范围查询:先用二分法,找到一个数据,然后向后遍历即。平均时间复杂度:O(log(N)) + O(N)
    • 维护成本:数组的插入和删除,平均时间复杂度:O(N)
    搜索树模型

    最基本的二叉树模型,为了维护查询效率,需要使用平衡二叉树。

    • 等值查询:二分法,平均时间复杂度O(log(N))
    • 范围查询:先用二分法,找到一个数据,然后向后遍历即。平均时间复杂度:O(log(N)) + O(N)
    • 维护成本:平均时间复杂度:O(log(N))
    总结:

    • 如果业务只需要等值查询:hash最适合
    • 如果业务中等值和范围查询都有:搜索树优于有序数组(维护成本方面)
    索引持久化后引发的问题

    如果索引都存储到内存中,上面的结论是足够的。我们知道,磁盘IO的成本是很高的,一旦将索引持久化到磁盘上后,对索引的数据结构选择就需要更多的考虑磁盘IO方面,磁盘IO次数越少越好。
    考虑刚才学习过的数据结构模型:

    • 二叉搜索树的数据结构决定了,假设树高为N层,平均磁盘IO次数为O(N),所以使用二叉树并不合适
    • 有序数组,查询时,需要查询出所有的索引数据块,然后才能进行二分法判断。

      • 假设一个数据块中存储10k的数据,一次IO可以取出一个块,一共有100K的索引,需要查询10次IO
        有序数组的磁盘IO是远远大于二叉搜索树的,这样看二叉搜索树的查询效率还可以

    有没有方法可以继续减少索引的IO次数?使用N叉树,一次IO可以查询出更多的索引进行对比,同时降低了树的高度,这样就可以减少磁盘的IO次数
    最佳实践


    • 可以通过建立索引,减少回表次数,这种操作成为覆盖索引(索引中数据都覆盖到了,不需要再回表查)
    • 可以通过最左前缀原则,减少索引的个数

      • 考虑联合索引的索引顺序时,可以考虑的原则

        • 通过调整顺序可以少维护索引
        • 字段所占空间大小


    • mysql在5.6版本以后,通过索引下推,来减少回表次数。当查询语句中有一部分使用到了索引,其他的查询条件需要回表查询判断。索引下推指的是,在回表前,先判断索引中是否已经包含了该字段,先过滤一次,如果不满足条件就不会回表了。
    • 如果表中经常删除数据,可以通过重建索引来减少索引维护产生的数据空洞,使数据更加紧凑

    Java吧 收集整理 java论坛 www.java8.com
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    快速回复 返回顶部 返回列表