云迈博客

您现在的位置是:首页 > 灌水专栏 > 正文

灌水专栏

Mysql索引底层数据结构

刘思佳2022-09-30灌水专栏44
Mysql的索引索引是帮助MySQL高效获取数据的排好序的数据结构。我们插入到数据表中的数据,有可能分布存储在磁盘不同的空间中,而我们的数据库查询的时候每次都要进行磁盘IO。当我们不加索引的时候,此时

Mysql的索引
索引是帮助MySQL高效获取数据的排好序的数据结构。
我们插入到数据表中的数据,有可能分布存储在磁盘不同的空间中,而我们的数据库查询的时候每次都要进行磁盘IO。当我们不加索引的时候,此时查询就是全表扫描,即一行一行的比对数据,多次进行磁盘IO,直到查询到我们所需的数据。
而我们所能想到的优化,自然是减少磁盘IO。而减少磁盘IO,我们自然是要减少数据比对的次数,即我们要在尽可能少的比对次数中,查询出我们需要的数据。
相关数据结构
二叉树
特点

  1. 至少有一个节点(根节点)。
  2. 每个节点最多有两颗子树,即每个节点的度小于3。
  3. 左子树和右子树是有顺序的,次序不能任意颠倒。
  4. 即使树中某节点只有一棵子树,也要区分它是左子树还是右子树。
    优点
    二叉树是一种比顺序结构更加高效地查询目标元素的结构,它可以从第一个父节点开始跟目标元素值比较,如果相等则返回当前节点,如果目标元素小于当前节点,则移动到左侧子节点进行比较,大于的情况则移动到右侧子节点进行比较,反复进行操作最终移动到目标元素节点位置。(左边元素都小于右边元素)

缺点
在大部分情况下,我们设计索引时都会在表中提供一个自增整形字段作为建立索引的列,在这种情况下使用二叉树的结构会导致我们的索引总是添加到右边,在查询记录时跟没加索引的情况一样(形成一个链表)

红黑树
红黑树是一种自平衡二叉搜素数(BST),且红黑树节点遵守
● 每个节点只能是黑色或黑色。
● 根节点肯定是黑色的。
● 红色节点的父或子节点都必然是黑色的(两个红色节点不会相连)。
● 任一节点到器所有后代NULL节点的每条路径都具有相同数量的黑色节点。
● 每个NULL节点都是黑色的。
优点
红黑树也叫平衡二叉树,它不仅继承了二叉树的优点,而且解决了上面二叉树遇到的自增整形索引问题,从下面的动态图中可以看出红黑树会走动对结构进行调整,始终保证左子节点数< 父节点数 < 右子节点数的规则。

缺点
在数据量大的时候,深度也很大。从图中可以看出每个父节点只能存在两个子节点,如果我们有很多数据,那么树的深度依然会很大,可能就会超过十几二十层以上,对我们的磁盘寻址不利,依然会花费很多时间查找。(树的层级太高,如果存在上亿的数据,那么依旧和链表类似)
hash表
优点
对数据进行Hash(散列)运算,主流的Hash算法有MD5、SHA256等等,然后将哈希结果作为文件指针可以从索引文件中获得数据的文件指针,再到数据文件中获取到数据,按照这样的设计,我们在查找where Col2 = 22的记录时只需要对22做哈希运算得到该索引所对应那行数据的文件指针,从而在MySQL的数据文件中定位到目标记录,查询效率非常高。很多时候Hash索引要比B+树索引更高效,但是仅能满足 “=” 或 “IN” 不支持范围查询(因为Hash冲突问题)
缺点
无法解决范围查询(Range)的场景,比如 select count(id) from sus_user where id >10;因此Hash这种索引结构只能针对字段名=目标值的场景使用。不适合模糊查询(like)的场景。

B-Tree
既然红黑树存在缺点,那么我们可以在红黑树的基础上构思一种新的储存结构。解决的思路也很简单,既然觉得树的深度太长,就只需要适当地增加每个树节点能存储的数据个数即可,但是数据个数也必须要设定一个合理的阈值,不然一个节点数据个数过多会产生多余的消耗。
● 度(Degree)-节点的数据存储个数,每个树节点中数据大于15/16*Degree(未验证)时会自动分裂,调整结构。
● 叶节点具有相同的深度,左子树跟右子树的深度一致。
● 叶节点的指针为空。
● 节点中的数据key从左到右递增排列。
树节点结构
BTree的结构里每个节点包含索引值和表记录的信息

优点
BTree的结构可以弥补红黑树的缺点,解决数据量过大时整棵树的深度过长的问题,相同数量的数据只需要更少的层,相同深度的树可以存储更多的数据,查询的效率更高。
缺点
在查询单条数据是非常快的,但如果范围查询的话,BTree结构每次都要从根节点查询一遍,效率会有所降低,因此在实际应用中采用的是另一种BTree变种,B+Tree(B+树)
B+Tree
● 非叶子节点不存储data值,只存储冗余索引,可以放更多索引。
● 叶子节点包含所有索引字段。
● 叶子节点用指针连接、提高区间访问的性能。

比较问题
BTree 和 B+Tree区别

  1. B+树的结构是根据B树的结构融合数据结构进行优化升级的。
  2. B+树的索引和数据存放在叶子节点上而B树每个节点都存储索引和数据。
  3. B树和B+树的数据都是从左到有递增,B+树叶子节点存在双向指针。指针的作用是:不同的叶子节点存储了其左右相邻的叶子节点的内存地址,这样可以非常快速的去访问相邻的叶子节点。
  4. B+树比B树可以存放更多的数据,因为数据都存在叶子节点而非叶子节点都只是索引值,控制了树的高度(相对于平衡二叉树)。
    B+树与Hash表的区别
  5. B+树和Hash表都可以作为索引的数据结构,一般来说都是使用B+树,B+树支持范围查询。
  6. Hash表不支持范围查询。

存储引擎
MyISAM
索引文件和数据文件是分离的(非聚集索引:索引和data值是分开的),并且主键索引和辅助索引(二级索引)的存储方式是一样的
.frm文件是存储:该表的数据表结构相关信息
.MYD文件是存储:该表的数据内容
.MYI文件是存储:该表的索引数据

引擎原理
1.col1(15值)存储的数据,会以b+树的格式进行存储myd里面
2.当查询某条数据,会到叶子节点找到相应索引值(15的索引值为0x07) 其实就是在myi里面找
3.在myi文件中找到索引值后,MyISAM引擎会根据索引值,到myd文件里面找到相应位置的值

Innodb
● 数据文件本身就是索引文件
● 表数据文件本身就是按B+Tree组织的一个索引结构文件
● 聚集索引-叶节点包含了完整的数据记录
Innodb索引文件(聚集索引:索引和data值是在一起的),并且主键索引和二级索引储存方式有所不同,如图所示,二级索引的叶子节点不储存数据,仅储存主键ID。
.frm文件是存储:该表的数据表结构相关信息
.ibd文件是存储:该表的索引和数据是存在一起的

联合索引

使用联合索引时,联合索引定义的顺序将会影响到最终查询索引的使用情况和结果,例如定义了联合索引(a,b,c) ,mysql会先从左边的列优先匹配,如果最左边定义的列都没有被使用到,在未使用覆盖索引的情况下,mysql就会默认执行全表扫描。
相关问题
问题一:为什么建议Innodb表必须建立主键?
首先构建索引的时候会去找到表中唯一的列,如果不存在唯一的列就会去构建一个虚拟的列,类似rowId,自己建立了主键就会去直接使用主键,更好的减少内存的消耗。
问题二:为什么主键推荐用整形而不是UUID?
索引为排好序的数据,主键为整形更容易排序、相对于UUID来说比较起来更快,同时占用空间更少。
问题二:为什么主键需要自增?

  1. 根据索引的相关需要将字段进行排序,为自增就不需要后面在强行将数据插入之前排好的列里面导致还需要分裂提取元素。
  2. Innodb存储引擎只允许一个聚集索引,如果不用主键递增的方式,那么我们自己建立的二级索引的叶子节点存放的就不是整行数据了。
    问题四:为什么非主键索引结构叶子节点存储的是主键值?
  3. 节约空间,存储更多的索引。
  4. 如果非主键索引的叶子节点也存储一份数据,如果通过非主键索引插入数据,那么要向主键索引对应的行数据进行同步,那么会带来数据一致性问题。可以通过事务的方式解决,我们都知道使用事务后,就会对性能有所消耗。

发表评论

评论列表

  • 这篇文章还没有收到评论,赶紧来抢沙发吧~