首页 数据库 mysql 正文

深入理解Mysql索引

long 2020-12-26 15:25 数据库 人气195

索引是一种数据结构,可以帮助我们快速的进行数据的查找。

索引的分类

从存储结构上来划分


    BTree索引(B-Tree或B+Tree索引)

    Hash索引

    full-test全文索引

    R-Tree索引


从应用层次来分


    普通索引:即一个索引只包含单个列,一个表可以有多个单列索引

    唯一索引:索引列的值必须唯一,但允许有空值

    复合索引:即一个索引包含多个列


根据中数据的物理顺序与键值的逻辑(索引)顺序关系


    聚集索引:表数据按照索引的顺序来存储的,也就是说索引项的顺序与表中记录的物理顺序一致。对于聚集索引,叶子结点即存储了真实的数据行,不再有另外单独的数据页。 在一张表上最多只能创建一个聚集索引,因为真实数据的物理顺序只能有一种。


    非聚集索引:表数据存储顺序与索引顺序无关。对于非聚集索引,叶结点包含索引字段值及指向数据页数据行的逻辑指针,其行数量与数据表行数据量一致。


索引的数据结构和具体存储引擎的实现有关, 在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的InnoDB存储引擎的默认索引实现为:B+树索引。


索引

Hash索引


基于哈希表实现,只有精确匹配索引所有列的查询才有效,对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),并且Hash索引将所有的哈希码存储在索引中,同时在索引表中保存指向每个数据行的指针。


索引


在MySQL中,只有 Memory 引擎显式支持哈希索引。这也是 Memory 引擎表的默认索引。


Hash索引的特点:


    hash索引是基于hash表实现的,只有查询条件精确匹配hash索引中的所有列的时候,才能用到hash索引。

    对于hash索引中的所有列,存储引擎都会为每一行计算一个hash码,hash索引中存储的就是hash码。

    hash索引包括键值、hash码和指针。


Hash索引的限制


因为hash索引本身只需要存储对应的hash值,所以索引的结构十分紧凑,这也让hash索引查找的速度非常快。然而,hash索引也是存在其限制的。


    Hash索引必须进行二次查找: 使用哈市索引两次查找,第一次找到相应的行,第二次读取数据,但是被频繁访问到的行一般会缓存在内存中,这点对数据库性能的影响不大。

    Hash索引不能用于外排序:hash索引存储的是hash码而不是键值,所以无法用于外排序

    Hash索引不支持部分索引查找也不支持范围查找,只能用到等值查询,不能范围和模糊查询

    Hash索引中的hash码的计算可能存在hash冲突:当出现hash冲突的时候,存储引擎必须遍历整个链表中的所有行指针,逐行比较,直到找到所有的符合条件的行,若hash冲突很多的话,一些索引的维护代价机会很高,所以说hash索引不适用于选择性很差的列上(重复值很多)。


B+树索引


索引


B+树底层实现是多路平衡查找树.对于每一次的查询都是从根节点出发,查找到叶子节点方可以获得所查键值,然后根据查询判断是否需要回表查询数据。


B+索引有几个关键特征:


    在叶子节点一层,所有记录的主键按照从小到大的顺序排列,并且形成了一个双向链表。叶子节点的每一个Key指向一条记录。

    非叶子节点取的是叶子节点里面Key的最小值。这意味着所有非叶子节点的Key都是冗余的叶子节点。同一层的非叶子节点也互相串联,形成了一个双向链表。


在MyISAM引擎中的实现


MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。


索引


在InnoDB中的实现


MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。


索引


基于这样一个数据结构,要实现下面的几个特性就很容易了:


    范围查询:比如要查主键在[1,17]之间的记录。二次查询,先查找1所在的叶子节点的记录位置,再查找17所在的叶子节点记录的位置(就是16所处的位置),然后顺序地从1遍历链表直到16所在的位置。

    前缀匹配模糊查询:假设主键是一个字符串类型,要查询where Key like abc%,其实可以转化成一个范围查询Key in [abc,abcz]。当然,如果是后缀匹配模糊查询,或者诸如where Key like %abc%这样的中间匹配,则没有办法转化成范围查询,只能挨个遍历。

    排序与分页:叶子节点天然是排序好的,支持排序和分页。


另外,基于B+树的特性,会发现对于offset这种特性,其实是用不到索引的。比如每页显示10条数据,要展示第101页,通常会写成select xxx where xxx limit 1000, 10,从offset =1000的位置开始取10条。


虽然只取了10条数据,但实际上数据库要把前面的1000条数据都遍历才能知道offset = 1000的位置在哪。对于这种情况,合理的办法是不要用offset,而是把offset = 1000的位置换算成某个max_id,然后用where语句实现,就变成了select xxx where xxx and id> max_id limit 10,这样就可以利用B+树的特性,快速定位到max_id所在的位置,即是offset=1000所在的位置。

常见问题

为什么建议自增长主键作为索引


结合B+Tree的特点,自增主键是连续的,在插入过程中尽量减少页分裂,即使要进行页分裂,也只会分裂很少一部分。并且能减少数据的移动,每次插入都是插入到最后。总之就是减少分裂和移动的频率。


插入连续的数据:


索引


插入非连续的数据


索引

最左前缀原则


例如对于下面这个表:


索引


如果我们按照 name 字段来建立索引的话,采用B+树的结构,大概的索引结构如下:


索引


如果我们要进行模糊查找,查找name 以“张”开头的所有人的ID,即 sql 语句为:


select `ID ` from `table` where `name` like '张%';


由于在B+树结构的索引中,索引项是按照索引定义里面出现的字段顺序排序的,索引在查找的时候,可以快速定位到 ID 为 100的张一,然后直接向右遍历所有张开头的人,直到条件不满足为止。


也就是说,我们找到第一个满足条件的人之后,直接向右遍历就可以了,由于索引是有序的,所有满足条件的人都会聚集在一起。


而这种定位到最左边,然后向右遍历寻找,就是我们所说的最左前缀原则。

主键索引和非主键索引


对于下面这个表,ID是主键,K为非主键索引:


索引


主键索引和非主键索引的示意图如下:


索引


其中R代表一整行的值。


从图中不难看出,主键索引和非主键索引的区别是:非主键索引的叶子节点存放的是主键的值,而主键索引的叶子节点存放的是整行数据,其中非主键索引也被称为二级索引,而主键索引也被称为聚簇索引。


根据这两种结构我们来进行下查询,看看他们在查询上有什么区别。


1、如果查询语句是 select * from table where ID = 100,即主键查询的方式,则只需要搜索 ID 这棵 B+树。


2、如果查询语句是 select * from table where k = 1,即非主键的查询方式,则先搜索k索引树,得到ID=100,再到ID索引树搜索一次,这个过程也被称为回表。

原文连接:https://gitlib.com/page/mysql-index.html
公众号
小程序
网站统计
  • 文章总数:249
  • 总点击量:35007
  • 评论总数:27
  • 网站运行:446 天