登录
原创

MySQL索引数据结构简介

发布于 2020-10-14 阅读 140
  • 后端
  • 数据库
  • MySQL
原创

1.什么是索引
索引是帮助MySQL高效获取数据的排好序的数据结构
索引结构

* 二叉树 不能自动归并 广度和深度不可控
* 红黑树 可以自动归并 但是每个节点只能存两个数据 深度不可控
* HASH 可以快速定位,但是无法进行大于小于和范围查询,部分索引可以适用
* BTREE 可以设置度,广度和深度可控

索引底层数据结构
B Tree

1. 度(Degree)-节点的数据存储个数
2. 叶节点具有相同的深度
3. 叶节点的指针为空
4. 节点中的数据key从左到右递增排列

Image.png

B+Tree

1. 非叶子节点不存储data,只存储key,可以增大度
2. 叶子节点不存储指针
3. 顺序访问指针,提高区间访问的性能

Image1.png
MySQL为什么使用B+tree 而不是B Tree
(1)B+树更适合外部存储(一般指磁盘存储),由于内节点(非叶子节点)不存储data,所以一个节点可以存储更多的内节点,每个节点能索引的范围更大更精确。也就是说使用B+树单次磁盘IO的信息量相比较B树更大,IO效率更高。
(2)mysql是关系型数据库,经常会按照区间来访问某个索引列,B+树的叶子节点间按顺序建立了链指针,加强了区间访问性,所以B+树对索引列上的区间范围查询很友好。而B树每个节点的key和data在一起,无法进行区间查找。
MyISAM索引实现(非聚集)
•MyISAM索引文件和数据文件是分离的
Image2.png
InnoDB索引实现(聚集)
•数据文件本身就是索引文件
•表数据文件本身就是按B+Tree组织的一个索引结构文件
•聚集索引-叶节点包含了完整的数据记录
Image3.png
联合索引的底层存储结构
Image4.png

评论区

阿满
4粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

2

0

2