mysql索引的数据结构

# 1. mysql早期的索引数据结构
![](/media/202206/2022-06-21_214232_306104.png)
假设一个如上图的表，现在想要以col1字段为索引。

## 1.1 二叉树
二叉树的原则是大值插在右侧，小值插在左侧。
那么当前表索引的结构就如下图。
![](/media/202206/2022-06-21_214645_534584.png)
这种极端的情况非常清楚的阐述了二叉树作为索引的劣势，即：==当新插入的值总是更大的值时，二叉树就变成了一个单向链表。==

## 1.2 红黑树
红黑树是一种二叉平衡排序树，它属于平衡树，但是却没有平衡二叉树那么“平衡”。
![](/media/202206/2022-06-21_215352_836885.png)
红黑树虽然解决了二叉树遇到自增时的情况，但是遇到数据量过大的情况时，红黑树的层数会过高，磁盘IO消耗较大。

## 1.3 hash表 
对索引的key做一次hash计算后定位到数据存储的位置。
哈希结构作为索引的速度非常快，甚至高于B+树。但是hash作为索引仅支持‘=’、‘IN’等操作，不支持范围查询；同时，还有hash冲突的问题。
![](/media/202206/2022-06-22_081945_960774.png)

# 2. B树与B+树
mysql当前使用B+树作为索引的数据结构。其中，B+树以B树为基础。

## 2.1 B树的特点
![](/media/202206/2022-06-21_220114_841433.png)
- 节点有排序。
- 一个节点中有多个元素，每个元素有顺序。

## 2.2 B+树的特点
![](/media/202206/2022-06-21_220205_582250.png)
- 节点有排序。
- 一个节点中有多个元素，每个元素有顺序。
- 叶子节点之间有指针。
- 根节点的数据都在叶子节点冗余了一份，且有顺序。

## 2.3 为什么mysql使用B+树
- B+树通过对数据进行排序可以提高查询速度的，
- 单个节点中可以存储多个元素，使得B+树的高度不会太高
- 叶子节点之间有指针，对全表扫描，范围查找等SQL语句很友好。

> 在Mysql中一个Innodb页就是一个B+树节点，一个Innodb页默认16kb。一般情况下一颗两层的B+树可以存2000万行左右的数据

# 3. B+树的应用-引擎
==各个表==在存储数据时有不同的存储方式，不同的储存方式有着不同的底层实现(如：存储机制，索引技巧，索引技巧，锁定水平)，底层实现的差异带来的功能也就不同。在不同的场景下使用合适的存储方式就能让数据读写速度更快或者获得额外的功能。

其中，InnoDB引擎和myISAM引擎都是用B+树作为索引。

索引值必须是唯一的，如果所有col都不是唯一的，mysql会创建一列隐藏的col来索引。

## 3.1 myISAM引擎相关的问题
.frm中储存表结构；.myd中储存数据；.myi储存表索引。

### myISAM引擎索引的工作方式
![](/media/202206/2022-06-21_222707_580971.png)

==非聚集索引==：索引与数据份文件存储。
叶子节点储存了数据的内存地址。
在索引文件.myi中查找到对应记录的内存地址后在.myd文件中取出对应的值。

## 3.2 InnoDB引擎相关的问题
.frm文件中储存表结构；.ibd文件中储存数据和索引。

### InnoDB引擎索引的工作方式
![](/media/202206/2022-06-21_222815_252003.png)
==聚集索引==：InnoDB引擎将数据和索引放在一起存储。比非聚集索引的方式速度快。

InnoDB引擎索引的叶子节点储存了索引以外的数据。

二级索引叶子节点的data储存的是主键，使用二级索引时，先找到主键，再通过主键去主键索引找到对应的记录。显然二级索引没有主键索引快。

### 为什么建议InnoDB引擎设置主键？主键类型为什么最好是且主键为整形自增？为什么不推荐UUID？
1. 由于B+树的特性，因此必须要有索引，且索引值必须是唯一的。没有索引，mysql会自行找一列所有记录都是唯一的col作为索引，如果所有col都不是唯一的，mysql会创建一列隐藏的col来索引。这样子会拖累mysql性能。因此使用InnoDB引擎推荐设置主键。
2. 使用整型时查找效率较高。使用整型自增主键在insert数据时永远都是往后面添加数据，大大降低了节点分裂的概率，进一步提高效率。
3. UUID为字符串类型的数据结构，查找效率较低，且浪费储存空间。

mysql索引的数据结构

【温馨提示：本站文档可配置可见范围，如登录后可见、对特定群组可见等，看不到就是没权限】

注册码获取邮箱
work@liuyaoze.com

mysql索引的数据结构

【温馨提示：本站文档可配置可见范围，如登录后可见、对特定群组可见等，看不到就是没权限】

注册码获取邮箱 work@liuyaoze.com

注册码获取邮箱
work@liuyaoze.com