Mysql索引底层数据结构之红黑树、B+树、Hash算法详解

2021-07-03 17:56:59   3  举报





Mysql索引底层数据结构之红黑树、B+树等算法详解

mysql索引优化

数据库

模版推荐

作者其他创作

大纲/内容

索引的概念

特点：先从索引文件中查找索引，然后通过索引索引对应的磁盘文件地址，再从数据文件中查找数据，索引文件和数据文件分开的，这样的索引也叫做非聚集索引，也称非聚簇索引

如果不设置主键呢？

底层也是一个B+树，那B+树如何组织这个联合索引呢

 为什么需要自增呢？B+树新加新的数据时，主键如果自增，B+树只需要在后面的节点依次新增新的节点存放数据，而且也会做一个新增节点和上一个节点的平衡，而主键不自增时，则会导致新的数据插入到之前的节点中，会和之前的节点进行比较，直至找到和新数据大小相邻的节点中，然后还会做一个新的平衡，而这个平衡则可能涉及很多节点索引的排序，效率会很低

IBD文件:存放索引和数据

节点

简单理解：B树索引和数据放在一起，B+树，索引和数据分开

frm:存储引擎

二级索引查询数据方式类似于非聚集索引，叶子节点存放的是索引和主键索引，比如Bob索引下面对应的是主键15索引，二级索引查找数据时，先根据二级索引找到主键索引，然后再到主键索引文件中的根节点依次查找到对应的数据

也是排好序的本质

如果不建主键，mysql则会从表中第一列数据开始，选择一列每个数据都不一样的列来组织B+树，如果选到最后都没有那样的一列，则会创建一个类似rowid的隐藏列来按照B+树的形式组织整张表的数据。

B+树

索引是mysql获取数据的排好序的数据结构

联合索引

在磁盘上分配一块很大的存储空间，用来存放很多索引key是字段值，value（data）是索引所在行在磁盘文件中地址

优点：一：查询深度低二：叶子节点和非叶子节点分开，非叶子节点只存放索引，叶子节点存放索引和数据，叶子节点存放的数据是每一行的数据三：每个叶子节点都用指针连接四：B+树的叶子节点和非叶子节点上的索引都是排好序的

查数据时，会通过磁盘的I/O来先获取保存索引的节点，然后加载到内存中，加载到内存中后，二分法比较节点中的索引大小，比如最终找到30这个数据，会在15——56之间，重新再进行一次磁盘I/O，将15——56之间的指向下一个节点的磁盘文件地址的节点重新加载到内存，依次类推，最终找到叶子节点中的30索引所在的磁盘文件地址，然后根据这个地址找到数据

B+树：mysql底层真正的数据结构！！！

InnoDB存储引擎

二叉树

没有索引的情况下，我想通过select * from t where t.Col2=89;这条数据，那么首先则会通过跟磁盘进行I/O操作，从磁盘读取数据，然后将会从第一行0x07这个文件地址依次往下查找对比，共需要查找6次，即全表扫描。而如果字段Col2加了索引之后，比如索引内部的数据结构使用的是二叉树，如上所示，Col2一列的值作为key，索引所在行的磁盘文件地址作为value，那么查询时，则仅需要通过比较两次key，就可以找到89

B树

select * from table where name ='Bill' and age='20';  只有这一条走索引   select * from table where age='20' and position='dev';select * from table where position='dev';

非叶子节点：一个节点包含多个索引+另一个节点在磁盘文件上的地址

一：IBD文件本身里面存放的是索引和数据就是按照B+树形式存放的，表数据文件本身就是按B+Tree组织的一个索引结构文件，而B+树从哪里来呢？如果说表里面主键自带主键索引，那么则就可以用主键自带的主键索引来组织整张表的索引数据

特点：虽然单边增长，但是会进行平衡，当右边的数大于左边的数时，会进行平衡，这样再查找6数字时，只需要查3次即可，比二叉树查询效率高出了一倍缺点：虽然红黑树可以自一定程度上提高查询效率，但是当数据量比较大的时候，红黑树的深度会越来越深，查询效率也在变得越来越慢

一个节点（一页）默认16KB，不推荐修改

为什么建议建主键？

索引底层是排好序的B+树数据结构，如果跳过了最左列字段name，则可能会产生当age进行范围查询时，右边的数据比左边的数据还要小的情况

为什么主键采用整型自增呢？

MYI文件:存放索引

这也是为什么DBA建议InnoDB表都建立一个主键列的原因，不然还要浪费mysql自身来消耗资源建立主键列

为什么要使用索引呢？

为什么采用整型呢？我们从根节点查找元素进行对比时，一：整型速度最快，字符和uuid相对较慢二：占用磁盘空间少

Mysql索引底层数据结构之红黑树、B+树、Hash算法详解