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

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

Mysql索引的底层数据结构

首先想清楚，什么是索引？它是一种

查询高效、排好序

常见的索引数据结构有：二叉树、红黑树、Hash表、B-Tree，mysql 索引的默认数据结构式是B+Tree，这是B-Tree的一个变种。

更深入地了解，我们需要区分几种数据结构的不同与优劣，这样才能明白为什么要选择B+Tree作为默认的索引结构。

区分不同索引结构

1. 二叉树

二叉树最坏的情况，所有的节点都在左侧，或者都在右侧。这样的单边增长，会让树的高度非常大，检索效率极低

2. 红黑树

红黑树能够一定程度上

自平衡

无法控制其深度

红黑树推荐文章：# 最易懂的红黑树讲解

3. B-Tree

观察上图可以发现B-Tree的一些特点：叶子节点具有相同的高度、节点中索引数据从左到右递增

4. B+Tree

对比B-Tree可以发现：B+Tree非叶子节点不存储数据，在叶子节点中包含了所有的索引数据。这样做的目的是，在固定大小的节点空间内能够存储更多的索引（对应存储更多的叶子节点数据）

另外，叶子节点之间前后以指针链接，这样访问后续叶子节点中的数据更加高效

5. Hash表

hash表的查询效率比B+Tree更高效，只需要一次hash计算就能定位到数据；

但是hash只能支持等值查询，如“=”、“in”，无法进行范围查询，此外存在hash冲突问题

区分Innodb与myisam存储引擎

MyISAM索引文件和数据文件是分离的(非聚集)，而Inonodb索引和数据在同一个文件中。

Innodb存储引擎中的一些特点：

表数据存储结构完全符合B+Tree的特点，数据只存储在聚集索引的叶子节点中。

区分是否聚集索引，就看索引和数据是否分离，辅助索引查询后根据主句ID，回表查询聚集索引。

为什么建表时必须建主键？

若是建表时没有建立主键，1.mysql会选择一列没有重复数据的作为主键，2.若不存在这样的列，则生成一个类似行号的作为主键。

这样无规则的字段作为主键是非常影响效率的。

推荐以整型自增主键，好处是方便比较大小，查询效率更高。

联合索引和最左前缀原则

创建联合索引的语法：key indexName (field1,field2,field3....) [using btree]

该索引树将依次按照字段1、字段2、字段3来排序。在索引树的叶子节点中包含了联合索引的所有字段，以及主键ID

最左前缀：

索引覆盖：