Mysql索引底层数据结构与算法

一时失言乱红尘 2022-09-10 10:26 170阅读 0赞

**索引是帮助MySQL高效获取数据的排好序的数据结构**

# **索引数据结构** #

> ## 二叉树 ##
> 
> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16][]
> 
> ## 红黑树 ##
> 
> ## Hash表 ##
> 
> > 对索引的key进行一次hash计算就可以定位出数据存储的位置
> > 
> > 很多时候Hash索引要比B+ 树索引更高效
> > 
> > 仅能满足 “=”，“IN”，不支持范围查询
> > 
> > hash冲突问题
> > 
> > ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 1][]
> 
> ## B-Tree ##
> 
> > 叶节点具有相同的深度，叶节点的指针为空
> > 
> > 所有索引元素不重复
> > 
> > 节点中的数据索引从左到右递增排列
> > 
> > ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 2][]
> 
> ## B+Tree(B-Tree变种) ##
> 
> > 主键索引（对应存储所有数据）
> > 
> > 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
> > 
> > 叶子节点包含所有索引字段
> > 
> > 叶子节点用指针连接(双向)，提高区间访问的性能
> > 
> > ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

# 索引 #

## MyISAM索引文件和数据文件是分离的(非聚集) ##

> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

##  InnoDB索引实现(聚集) ##

> 表数据文件本身就是按B+Tree组织的一个索引结构文件
> 
> 聚集索引-叶节点包含了完整的数据记录
> 
> 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
> 
>        （InnoDB默认会创建id自增主键方便B+tree排序）
> 
> 为什么非主键索引结构叶子节点存储的是主键值？
> 
>        (一致性和节省存储空间)
> 
> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 5][]
> 
>  ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

## 联合索引的底层存储结构 ##

> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/70a76853bce642bcbc5438b04ab3c2a7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/b0f90fd45347402c8bc73287f2b6d362.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/bad3e7f0e0754b439e7a7300dbb6de7e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/8f895a5e529041c8a1596863e4faf723.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/56b77ae8692c4cbf8ea7c8486b723f24.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/0c3ffb62ae4148f8923d4f3745f410f6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/08039cf8f4b94aab91509d5992ce0500.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQS1lenJ6_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220829/360f47382ea04963985dc6704fe77012.png