• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Mysql的索引机制一

互联网 diligentman 2周前 (05-01) 7次浏览

索引的出现是为了提高查询效率,Mysql索引是B+tree

目录

一、索引的常见数据结构
二、InnoDB的索引模型
三、索引的维护
四、名词与相关概念解释


一、索引的常见数据结构

  • 哈希表:
    以键值对存储数据的结构,缺点会发生hash突出,后面跟着的链表和数组,使得哈希表结构适用于等值查询的场景。

  • 二叉树:
    二叉树是搜索效率最高的,时间复杂度是 O(log(N)),为了维持 O(log(N)) 的查询复杂度,得保持这颗树是一颗平衡二叉树。

  • B+树:
    索引不止存在内存中,还要写到磁盘上。二叉树的深度比较深,读取磁盘需要时间,所有引出了N叉树降低磁盘访问开销。

返回顶部目录


二、InnoDB的索引模型

  • InnoDB 使用了 B+ 树索引模型,所以数据都是存储在 B+ 树中的

  • 每一个索引在 InnoDB 里面对应一棵 B+ 树

  • 假设,我们有一个主键列为 ID 的表,表中有字段 value,并且在 value上有索引。

    mysql> create table T
    (id int primary key,
     value int not null, 
     name varchar(16),
     index (value)
     )engine=InnoDB;
    

    表中 R1~R5 的 (ID,value) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),两棵树的示例示意图如下。
    Mysql的索引机制一

    • 根据叶子节点的内容,索引类型分为主键索引和非主键索引。

    • 主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。

    • 非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

    • 例子:主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。根据上面的索引结构说明,我们来讨论一个问题:基于主键索引和普通索引的查询有什么区别?如果语句是 select * from T where ID=500,即主键查询方式,则只需要搜索 ID 这棵 B+ 树;如果语句是 select * from T where value=5,即普通索引查询方式,则需要先搜索 value 索引树,得到 ID 的值为 500,再到 ID 索引树搜索一次。这个过程称为回表。也就是说,基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。

返回顶部目录


三、索引的维护

  • 在上面的表中,如果新插入的行ID值为400,需要逻辑上挪动后面的数据,空出位置。
  • 如果那个数据页数据满了,根据 B+ 树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去。这个过程称为页分裂。在这种情况下,性能自然会受影响。
  • 基于上面的问题,我们在很多建表规范中,都有这样的描述,建表需要一定要有自增主键。
    • 每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂。
    • 而有业务逻辑的字段做主键,则往往不容易保证有序插入,这样写数据成本相对较高。
  • 由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号等做主键,那么每个二级索引的叶子节点占用约 20 个字节,而如果用整型做主键,则只要 4 个字节,如果是长整型(bigint)则是 8 个字节。主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。
  • 业务字段直接做主键的(典型的kv场景),可以避免每次查询需要回表搜索两棵树:
    • 只有一个索引;
    • 该索引必须是唯一索引。

返回顶部目录


名词与相关概念解释

  • 为什么数据库存储使用b+树 而不是二叉树?

    • 因为二叉树树高过高,每次查询都需要访问过多节点,即访问数据块过多,而从磁盘随机读取数据块过于耗时。
    • 一页就是B-tree上的一个节点,因为根节点总是在内存,所以查找一个值最多进行树高h-1次磁盘io就能找到。
    • 虽然平衡二叉树时间复杂度低,但树深度可能较深,每一个层级的访问都伴随着磁盘的访问。
  • 为什么 “N 叉”树中的“N”取决于数据块的大小?

    • 一个数据块假如有500 字节,一个子节点的索引地址大小是10个字节,那么这个节点就可以存储50个孩子节点的索引,这个树就是50叉树,所以 N取决于数据块的大小。
  • 为什么 InnoDB整数字段索引的b+树最大能维持大约1200叉树

    • MySql默认一个节点的长度为16K,一个整数(bigint)字段索引的长度为 8B,另外每个索引还跟着6B的指向其子树的指针;所以16K/14B ≈ 1170
  • 比较新的数据结构

    • redis 中使用到跳表,hbase memstore 和flink中的rocksdb使用到LSM树
  • 关于 InnoDB 的表结构:

    • 1.在 InnoDB 中,每一张表其实就是多个 B+ 树,即一个主键索引树和多个非主键索引树。 2.执行查询的效率,使用主键索引 > 使用非主键索引 > 不使用索引。 3.如果不使用索引进行查询,则从主索引 B+ 树的叶子节点进行遍历
  • 回表:

    • 主键索引的b+树的叶子节点存储的是具体的行数据,非叶子节点存储的是主键的值。叶子节点之间通过链表连接 非主键索引的叶子节点存储的是主键的值,所以通过非主键索引查询数据时,先找到主键,再去主键索引上根据主键找到具体的行数据
  • 根据具体需求选择合适的结构

    • 二叉树也会畸变成单链表,所以才有了AVL树通过旋转的方式来维持树的平衡,但后来发现大量的旋转实在是性能不好,所以有了红黑树。都是二叉树,只是约束条件不一样。没有最好的方法只有更适合的方法,要维持某一方面的优势需要牺牲另一方面的优势,就看如何选择了。

程序员灯塔
转载请注明原文链接:Mysql的索引机制一
喜欢 (0)