

首页  思维笔记  详情



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

2022-12-07 14:26:02   2  举报





仅支持查看

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

性能调优专题

模版推荐

作者其他创作

大纲/内容

索引

是帮助Mysql高效获取数据的排好序的数据结构

索引数据结构

以下图数据表查询为例：

二叉树

二叉树结构：

二叉树示意图：

与不使用索引时比较：

以查询Col2=89为例，此列数据为非连续非顺序的

在不使用索引情况查询，需要查找6次后可得到结果，如下图所示：

使用二叉树结构查询，仅需要查找2次即可得到结果，如下图所示：

但Mysql索引底层数据结构并未采用二叉树结构

原因1：

以查询Col1=6为例（此列数据是顺序递增的）

在使用二叉树情况下查询，需要查找6次后才可得到结果，如下图所示：

此时，与未使用索引情况下时查询次数一样，并未提高查询效率

原因2：

在百万级数据量或更高的情况下，二叉树层级过多，树的高度不可控，会很高很高，当查询结果为叶子节点时查询效率下降明显

红黑树

红黑树结构：

红黑树结构示意图1：

红黑树结构示意图2：

与使用二叉树时比较：

以查询Col1=6为例，此列数据是顺序递增的

在使用二叉树情况下查询，需要查找6次后才可得到结果，如下图所示：

在使用红黑树情况下查询，只需要查找3次就可得到结果，如下图所示：

相对二叉树来说，红黑树对于单边操作时，他会做一次平衡

但Mysql索引底层数据结构也并未采用红黑树结构

原因：

在百万级数据量或更高的情况下，与二叉树一样，层级过多，树的高度不可控，会很高很高，当查询结果为叶子节点时查询效率下降明显

B-Tree

B-Tree结构：

B-Tree示大体意图：

B-Tree示细节意图：

B-Tree特征：

叶子节点具有相同的深度，叶子节点的指针为空

所有索引元素不重复

节点中数据索引从左到右递增排列

与红黑树、二叉树比较：

以查询Col2=89为例（此列数据为非连续非顺序的）

使用B-Tree结构查询，也仅需要查找2次即可得到结果，如下图所示：

以查询Col1=6为例（此列数据为连续递增的）

使用B-Tree结构查询，仅需要查找2次即可得到结果，如下图所示：

但Mysql索引底层数据结构也并未采用B-Tree结构

原因：

由B-Tree示细节意图，可看出每个节点存放data会占用节点资源，减少节点中的索引元素数量，在大数据量时会增加树的层级，即增加了查找次数。

B-Tree 进行数据范围查询时，由于节点之间未使用指针连接，范围查询每次都需要从根节点开始查找。

B+Tree

B+Tree结构：

普通的B+Tree示意图：

MySQL改造的B+Tree示意图2：

B+Tree特征：

非叶子节点不存储data，只存储(冗余)索引，这样可以放更多的索引

叶子节点包含所有索引字段

叶子节点用指针连接，提高区间访问的性能

与普通的B+Tree相比，MySQL改造的B+Tree的叶子节点之间为双向指针连接

与B-Tree相比较：

1、B+Tree非叶子节点不存储data，比B-Tree可以存放更多的索引，差异如下图：

a. B-Tree结构图：

b. B+Tree结构图：

2、B+Tree非叶子节点只存储冗余的索引，差异如下图：

a. B-Tree结构图：

b. B+Tree结构图：

3、B+Tree叶子节点包含所有索引元素，而B-Tree所有节点包含所有索引元素，差异如下图：

a. B-Tree结构图：

b. B+Tree结构图：

4、B+Tree叶子节点之间使用双向指针连接，而B-Tree节点之间没有使用指针连接，差异如下图：

a. B-Tree结构图：

b. B+Tree结构图：

Mysql索引底层数据结构采用是MySQL改造后的B+Tree结构

Hash表

Hash表结构：

Hash表示意图：

Hash表特征：

对索引的key进行一次hash计算就可以定位出数据存储的位置

很多时候Hash索引要比B+Tree索引更高效

仅能满足 “=”，“IN”，不支持范围查询

Hash存在冲突问题

与B+Tree相比较：

以查询Col2=89为例（此列数据为非连续非顺序的）

使用Hash表结构查询，仅需要1次即可得到结果，如下图所示：

不建议使用Hash表结构的原因：

a. 仅能满足 “=”，“IN”，不支持范围查询

b. Hash存在冲突问题

存储引擎索引实现

MyISAM存储引擎索引实现

MyISAM存储引擎产生的对应的数据库文件（3个）

如下图所示：

MyISAM索引文件和数据文件是分离的（非聚集）

如下图所示：

InnoDB存储引擎索引实现

InnoDB存储引擎产生的对应的数据库文件（2个）

如下图所示：

InnoDB索引文件和数据文件是在一起的（聚集）

如下图所示（主键/聚簇索引结构）：

如下图所示（二级/辅助索引结构）：

由上图可知：

1、表数据文件本身就是按B+Tree组织的一个索引结构文件

2、聚集索引——叶子节点包含了完整的数据记录

为什么建议InnoDB表必须建主键？并且推荐使用整型的自增主键？

1.1 InnoDB表必须建主键，因主键索引叶子节点包含了完整的数据记录，所以有且必须存在一个主键索引

1.2 InnoDB表必须建主键，a. 当未设置主键时MySQL底层会通过筛查把数据唯一的字段作为主键来创建主键索引，b. 当也不存在该数据唯一列时，底层会新建一个rowid的虚拟字段作为主键索引字段，因此更建议由我们自己来建主键

2.1 推荐使用整型的主键，是因为整型主键占用空间小，比对查询效率比其他类型（其他类型需要hash后才进行比对）的高

2.2 推荐使用整型自增的主键，是因为索引数据结构节点中的元素是从左到右依次顺序递增的，当新增索引元素时底层需要比对后插入且可能会发生数据结构再平衡操作，相对自增的主键插入效率更高点

为什么非主键索引结构叶子节点只存储的data是主键值？

1. 数据一致性

2. 节省存储空间（主要原因）

索引最左前缀原理

索引最左前缀原理，主要应用于“联合索引”。

联合索引的底层结构：

索引最左前缀原理的实际应用说明：

指：对以含联合索引的第一个（最左侧）的索引字段的查询有效

以t_user表，联合索引为 KEY `idx_name_age_position` (`name`, `age`, `position`) USING BTREE 为例：

实际应用有效情景：

应用1：select * from t_user where name = 'Lilei' and age = 30 and position = 'dev';

应用2：select * from t_user where name = 'Lilei' and age = 30;

应用3：select * from t_user where name = 'Lilei' and position = 'dev';

实际应用<strike>无效</strike>情景：

应用1：select * from t_user where age = 30 and position = 'dev';

应用2：select * from t_user where age = 30;

应用3：select * from t_user where position = 'dev';

 Collect

Get Started

数据结构与算法

 Collect

Get Started

Mysql索引数据结构与算法

 Collect

Get Started

数据结构与算法

 Collect

Get Started

数据结构与算法





0 条评论

下一页