深入理解Mysql索引底层数据结构与算法

索引是什么？

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

索引的好处？

假设我们有一个表t，它有俩个字段，Col1和Col2，如下：

• 不加索引

不加索引的情况下，SQL：select * from t where t.col2 = 89，需要从表的第一行开始一行一行地遍历对比col2的值是否等于89，这样需要比对6次才能查到。这还是只有几行记录的表，那如果是百万级千万级的表呢？是不是就比较的次数就更多了，那还不得慢死。

• 加索引

col2这列加了索引，mysql内部会维护一个数据结构。假设mysql用的数据结构是红黑树（右子树的元素大于根节点，左子树的元素小于根节点）的数据结构建立索引，那就像上图右边那样。这样的话，刚才的那条SQL是不是只需要2次磁盘IO就查到了，是不是快很多了。这就是索引的好处。索引使用比较巧妙的数据结构，利用数据结构的特性来大大减少查找遍历次数。

索引数据结构

• 二叉树
• 红黑树
• hash
• B-tree

二叉树

把如上图col1作为索引，col1这列的数据特点是从上到下依次递增，类似于自增主键，那在每插入一行在维护二叉树这样一个数据结构的时候退化成了链表。

红黑树

是一种平衡二叉树，JDK1.8的HashMap就用到了红黑树，存储大数据量，树的高度不可控， 数量越大，树的高度越高影响查询效率。

hash

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

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

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

hash冲突问题

B-tree

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

所有索引元素不重复

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

B+Tree（B-Tree变种）

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

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

叶子节点用指针连接，提高区间访问的性能(B-Tree没有)

存储引擎

InnoDB 存储引擎两个文件分别存储：

frm（framework）：表结构文件

ibd（innodb data）：表索引及数据文件

MyISAM 存储引擎三个文件分别存储：

frm（framework）：表数据结构文件

MYI（myisam index）：表索引文件

MYD（myisam data）：表数据文件

MyISAM索引实现(非聚集)

MyISAM索引文件和数据文件是分离的(非聚集)，结构如图。

InnoDB索引实现(聚集)

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

聚集索引-叶节点包含了完整的数据记录

为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

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

因为如果我们没有自己设立自增主键，那么InnoDB就会自动帮我们选一个列的所有的数据不一样的属性作为主键（组织我们的B+树），如果表中不存在这样的列，那么InnoDB就会帮我们创建一个隐藏列。

使用整型的原因是在对比的时候，整型的比较速度更快（1<2），如果使用的是字符串，还要转换为ASCLL码，并且整型的占用空间比较小。

使用自增的主键原因是如果不是自增的，容易改变索引的结构，降低效率。

二级索引(辅助索引)

以 ALTER TABLE test_innodb ADD INDEX idx_name(name) USING BTREE;为例，建立二级索引 B+tree

二级索引在构建索引时叶子结点数据仅存放索引和主键 ID，并且以索引 name 字段来排序作为叶子节点关键字，那么例如要 SELECT * FROM test_innodb WHERE name = 'Alice'; ，那么会怎么查找呢？

首先，会通过二级索引idx_name(name) 查询到 Alice，得到叶子结点主键 ID 为18后，会通过18去主键索引构建的 B+tree 中查询所有字段信息，这也就是所谓的 回表。

联合索引(复合索引)

可以看到，联合索引建立 B+tree 时，会以建立索引的顺序来排列数据，首先以 name 字段排序，再以 age 字段来排序。name 字段值如果相同，例如Bill 那么就会以 age 来排列顺序，以此类推，最终同样查到相应的主键 ID 之后回表到以主键构建的 B+tree 中查询完整的行信息。

看完联合索引结构，想必客官已经知道最佳左前缀原则是为什么第一个字段(name)一定要有才能生效了，因为只有第一个字段相同，第二个字段(age)才是有顺序排列的。

同时如果同时存在两个索引 idx_name(name)和 idex_name_age(name, age)，那么 idx_name(name)即为冗余索引，在建立索引时只需要建立联合索引idex_name_age(name, age)。

B树和B+树的区别

（1）B树不管叶子节点还是非叶子节点，都会保存数据，而B+树只会在叶子节点存储数据

（2）B树叶子结点的指针是单向的，而B+树是双向的

MySQL的底层索引为什么要选B+树而不是B树

因为B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少（有些资料也称为扇出）

指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低；

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/08/11 11:16:15