深入解析MySQL索引数据结构

目录
    • b-tree
    • b+tree
    • hash
    • innodb 索引实现(聚集)

      概述

      索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。

      索引数据结构

      二叉树

      二叉树(binary tree)是指树中节点的度不大于 2 的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树

      对于数组 {1,2,3,4,5} 数据结构将成为了链表

      特点:

      • 父节点下面有两个子节点。
      • 右边节点的数据大于左边节点的数据。

      二叉树.png

      红黑树

      红黑树是一种特定类型的二叉树,它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树,则它的任一子树必为红黑树。

      红黑树是一种平衡二叉查找树的变体,它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉树(avl),但对之进行平衡的代价较低, 其平均统计性能要强于 avl 。

      由于每一棵红黑树都是一棵二叉排序树,因此,在对红黑树进行查找时,可以采用运用于普通二叉排序树上的查找算法,在查找过程中不需要颜色信息。

      红黑树数据结构如下图:

      红黑树数据结构.png

      特点:

      • 红黑树是每个结点都带有颜色属性的二叉查找树,颜色或红色或黑色。
      • 结点是红色或黑色。
      • 根结点是黑色。
      • 所有叶子都是黑色。(叶子是nil结点)
      • 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
      • 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
      • 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
      • 是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。
      • 因为红黑树是一种特化的二叉查找树,所以红黑树上的只读操作与普通二叉查找树相同。

      b-tree

      • 叶子结点具有相同的深度,叶节点的指针为空
      • 所有元素不重复
      • 节点中的数据索引从左到右边递增排列

      b树数据结构.png

      b+tree

      • 非叶子结点不存储数据,只存储索引(冗余),可以存放更多的索引
      • 叶子结点包含所有索引字段
      • 叶子结点用指针链接,提高区间访问的性能(可以提升范围查找的效率)

      b+树数据结构.png

      特点关键字:节点内有序,叶子结点指针链接,非叶子结点存储索引(冗余)

      查询mysql 索引的数据页的大小:

      mysql> show global status like 'innodb_page_size';
      +------------------+-------+
      | variable_name    | value |
      +------------------+-------+
      | innodb_page_size | 16384 |
      +------------------+-------+
      

      为什么设置 16kb 呢?

      hash

      • 对索引的 key 进行一次 hash 计算就可以定位出数据存储的位置
      • 很多的时候 hash 索引要比 b+ 树索引更高效
      • 仅能满足 “=” , “in”  不支持范围查询
      • 存在 hash 冲突问题

      hash 数据结构.png

      索引

      innodb 索引实现(聚集)

      表数据文件本身就是按 b+tree 组织的一个索引结构文件

      聚集索引-叶子节点包含了完整的数据记录

      为什么 innodb 表必须有主键,并且推荐使用整型的自增主键?

      • 如果没有设置索引的话,mysql 会选择一个数据唯一的列作为主键索引, 如果找不这样的列。会去做创建一个隐藏列类似  rowid。
      • 表数据文件按照 b+tree 的数据结构维护,在叶子节点维护的是该行的数据。所以必须有主键。
      • 整型更方便 b+tree 排序,自增的话,对于数据结构的存放更快,  顺序存放,不需要进行大量树的平衡操作。

      为什么非主键索引结构叶子节点的存储的是主键值?

      • 一致性, 让主键索引先成功,然后再去更新非主键索引关系
      • 节省存储空间。

      主键索引示意图:

      innodb 索引实现.png

      非主键索引示意图图片

      如果查询的是通过 name = alice 去查询的时候:

      1. 走非主键索引去查询,查询完后拿到信息(alice, 18)。其实这里也是一个非聚簇索引
      2. 然后进行回表查询,再次通过主键去查询做回表查询。

      两个数据文件:

      .frm 主要是存储表结构信息

      .ibd 主要是存储索引和数据

      myisam 索引文件(非聚集)

      索引文件和数据文件是分离的(非聚集)

      myisam 存储引擎索引.png

      三个数据文件:

      .frm 数据结构文件

      .myd 文件主要是存储数据

      .myi 文件主要是存储索引信息

      聚集索引和非聚集索引

      特征:

      聚集/非聚集主要是索引文件是否和数据文件在一起。

      查询效率上来说聚集索引不会跨文件查询效率会更加快。

      联合/复合索引

      多个字段组织成一个共同的索引

      组合索引.png

      最左前缀原理为什么这样来使用?

      索引的数据是被排序的,如果跳过字段的话是无法被使用的。

      示例:

      where name = 'jeff' and age = 22              -- 命中索引
      
      where age = 30  and postatin='manager'  -- 不命中索引
      
      where postation = 'dev'                            -- 不命中索引
      
      

      参考资料

      百度百科

      总结

      到此这篇关于mysql索引数据结构的文章就介绍到这了,更多相关mysql索引数据结构内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com!

      (0)
      上一篇 2022年3月21日
      下一篇 2022年3月21日

      相关推荐