【mysql】聚簇索引和非聚簇索引（B树和B+树）_Mysql

hash表，在java中的hashmap，treemap就是hash表结构，以键值对的方式存储数据。我们使用hash表存储表数据key可以存储索引列，value可以存储行记录或者行磁盘地址。hash表在等值查询时效率很高，时间复杂度为o(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

2.1 b树：改造二叉树

mysql的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘io操作非常耗时，所以我们优化的重点就是尽量减少磁盘io操作。访问二叉树的每个结点就会发生一次io，如果想要减少io操作，就需要降低树的高度。

假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8+4*2=16）。

因为在mysql的innodb存储引擎一次io会读取的一页（默认一页16k）的数据量，而二叉树一次io有效数据量只有16字节，空间利用率极低。为了最大化利用一次io空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000*1000=1百万），也就是说只需要2次磁盘io就可以查询到数据。磁盘io次数变少了，查询数据的效率也就提高了。

这种数据结构我们称为b树，b树是一种多叉平衡查找树，如下图主要特点：

b树的节点中存储着多个元素，每个内节点有多个分叉。
节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
父节点当中的元素不会出现在子节点中。
所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

在这里插入图片描述

举个例子：

过程如图：

在这里插入图片描述

看到这里你一定觉得b树很理想了，但是b树不支持范围查询的快速查找，如果我们想查询15-30之间的数据，查到15之后，我们还要返回根节点重新遍历查找下一个数据，直到全部遍历找到。

如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘io次数就会变大。

2.2 b+树：改造b树

b+树，作为b树的升级版，在b树基础上，mysql在b树的基础上继续改造，使用b+树构建索引。b+树和b树最主要的区别在于非叶子节点是否存储数据的问题

在这里插入图片描述

mysql的索引就采用了b+树的数据结构。

三、mysql索引实现—innodb引擎

3.1 主键索引（聚簇索引）

聚集索引：指索引项的排序方式和表中数据记录排序方式一致的索引。聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。

每个innodb表都有一个聚簇索引，聚簇索引使用b+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，innodb会自动创建一个rowid字段来构建聚簇索引。

除聚簇索引之外的所有索引都称为辅助索引。在中innodb，辅助索引中的叶子节点存储的数据是该行的主键值。在检索时，innodb使用此主键值在聚簇索引中搜索行记录。

在这里插入图片描述

select * from user_innodb where id = 28;

在这里插入图片描述

先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘io）
将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘io）
检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于28的索引项，直接可以获取整行数据。将改记录返回给客户端。（1次磁盘io）

磁盘io数量：3次。

3.2 辅助索引（非聚簇索引）

非聚集索引：索引顺序与物理存储顺序不同

在这里插入图片描述

除聚簇索引之外的所有索引都称为辅助索引，innodb的辅助索引只会存储主键值而非磁盘地址.

在这里插入图片描述

使用辅助索引需要检索两遍索引：首先检索辅助索引获得主键，然后使用主键到主索引中检索获得记录。

select * from t_user_innodb where age=19;

在这里插入图片描述

根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询。

磁盘io数：辅助索引3次+获取记录回表3次

3.3 避免回表

在innodb的存储引擎中，使用辅助索引查询的时候，因为辅助索引叶子节点保存的数据不是当前记录的数据而是当前记录的主键索引，索引如果需要获取当前记录完整数据就必然需要根据主键值从主键索引继续查询。这个过程我们成位回表。想想回表必然是会消耗性能影响性能。那如何避免呢？

使用索引覆盖，举个例子：现有user表（id(pk),name(key),sex,address,hobby…）

如果在一个场景下，select id,name,sex from user where name ='zhangsan';这个语句在业务上频繁使用到，而user表的其他字段使用频率远低于它，在这种情况下，如果我们在建立 name 字段的索引的时候，不是使用单一索引，而是使用联合索引（name，sex）这样的话再执行这个查询语句是根据辅助索引查询到的结果就可以获取当前语句的完整数据。这样就可以有效地避免了回表再获取sex的数据。

3.4 覆盖索引

覆盖索引并不是说是索引结构，覆盖索引是一种很常用的优化手段。因为在使用辅助索引的时候，我们只可以拿到主键值，相当于获取数据还需要再根据主键查询主键索引再获取到数据。但是试想下这么一种情况，在上面abc_innodb表中的组合索引查询时，如果我只需要abc字段的，那是不是意味着我们查询到组合索引的叶子节点就可以直接返回了，而不需要回表。这种情况就是覆盖索引。

覆盖索引的情况：
在这里插入图片描述