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

索引的概念

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

如果不设置主键呢？

底层也是一个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算法详解

MyISAM存储引擎

索引的几种数据结构

可不可以将索引查询的深度只保持在比如说小于4，小于5，但是可以容纳几千万以上的数据呢？

存储引擎

Hash

面试题：为什么mysql索引选择B+树，而不是B树呢？

MYD文件:存放数据

红黑树

特点：先比较索引，然后找到要寻找的索引地址，找到后，直接将索引所在行的数据通过磁盘I/O拿到内存即可。索引和数据在一个文件中，叶子节点包含索引和数据，这样的索引叫做聚集索引，也称聚簇索引

复合索引:多个字段建立的一个共同索引

缺点：二叉树仍有可能全表扫描，比如第一列加索引情况下，序号是一直递增的，想要查到6数字，则需要查询6次，变为链表结构，查询效率很慢

聚集索引相对效率更高，因为聚集索引和数据在一起，找到索引时就可以直接找到数据，二非聚集索引则是在找到索引后还需要跨文件到数据文件中查找数据

联合索引索引最左列原则！！！

为什么只走最左列的索引呢？

Bob