MySQL Index 之 B+Tree数据结构

MySQL中90%的慢Sql都可以通过索引来得到优化,为什么索引可以使Sql变的更快,我们需要先了解下MySQL InnoDB都有哪些索引。

按规则分类:

Hash索引

Memory引擎默认

USING HASH

BTREE索引

InnoDB引擎默认B+Tree

USING BTREE

按类型分类:

主键

也叫聚集索引,不允许有Null值

唯一索引

同主键,但允许有Null值

二级索引

辅助索引

全文索引

MySQL5.6以后才支持,且只能是char、varchar,text字符类型才可以创建全文索引

复合索引

多列联合的索引,可以是主键,也可以是辅助索引

数据结构:

不管哪种索引,都是一种数据结构。

哈希表

字段值通过Hash算法得出的Hash码,Hash索引中存储的即Hash码

二叉树

每个节点包含左右指针、键值、存储地址,左子树的键值小于根的键值,右子树的键值大于根的键值

平衡二叉树

每个节点包含左右指针、键值、存储地址,左子树的键值小于根的键值,右子树的键值大于根的键值,两个子树的高度最大差为1

BTree

非叶子节点也存储数据,无双向链指针

B+Tree

只有叶子节点存储数据,有双向链指针

哈希表:

哈希索引就是采用一定的哈希算法,把键值换算成新的哈希值,同时在哈希表中保存指向每个数据行的指针。检索时不需要类似B+Tree那样从根节点到叶子节点逐级查找,只需一次哈希算法即可定位到相应的位置,速度非常快。但优势只适用于键值唯一的等值查询。

二叉树与平衡二叉树:

二叉树:可以任意地构造,高度越大效率越低,以下6个值平均查找次数为(1+2+3+4+5+5)/ 6 = 3.3 次IO。

平衡二叉树:平衡二叉树简称平衡树,是由Adelson-Velskii和Landis于1962年首先提出的,所以又称为AVL树。在符合二叉树的条件下,还满足任何节点的两个子树的高度最大差为1,以下6个值平均查找次数(1+2+2+3+3+3)/ 6 = 2.3 次IO。

缺点:

大量删除、新增会导致频繁旋转;

实际运用较少,主要用于数据结构研究。

BTree:

BTree是为磁盘存储而专门设计的一类平衡搜索树,文件系统和数据库系统一般都采用BTree的数据结构,主要为提升排序和检索的效率。

由于BTree的所有节点都存储数据,这就限制了BTree节点拥有孩子节点个数,如果数据量特别大,会导致树的高度变高,IO就会增多。

模拟查找关键字29的过程:

  1. 根据根节点找到磁盘块1,读入内存。【磁盘I/O操作第1次】
  2. 比较关键字29在区间(17,35),找到磁盘块1的指针P2。
  3. 根据P2指针找到磁盘块3,读入内存。【磁盘I/O操作第2次】
  4. 比较关键字29在区间(26,30),找到磁盘块3的指针P2。
  5. 根据P2指针找到磁盘块8,读入内存。【磁盘I/O操作第3次】
  6. 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程,发现需要3次磁盘I/O操作,和3次内存。

但如果我们想进行范围查找,查询10~79之间的数据,就需要从跟节点一个一个往下查,范围跨度越大,则磁盘IO的次数就越多,性能越差。因此在BTree的基础上就有了B+Tree。

B+Tree:

B+Tree是在BTree基础上的一种优化,使其更适合实现外存储索引结构,InnoDB存储引擎就是用B+Tree实现其索引结构。

B+Tree相对于BTree有几点不同:

  1. 非叶子节点只存储键值信息。
  2. 所有叶子节点之间都有一个双向链指针。
  3. 数据记录都存放在叶子节点中。

这样索引树不用太高,就能满足需要对数据的检索需求,使查询更快速,例如:

定义一棵B+Tree,高度h = 3;

我们知道MySQL InnoDB默认数据页大小为16k;

MySQL root@[mysql]>show global status like 'Innodb_page_size';+------------------+-------+| Variable_name    | Value |+------------------+-------+| Innodb_page_size | 16384 |+------------------+-------+

假设字符集为utf8,在一个int字符类型的字段加索引(int固定占4个字节);

一个Page除去页号、页类型等10个字节(如下图);

非叶子节点存储键值(扇出系数) = 16384 / (4+10) = 1170 个Key;

所以在高度h=3时,索引里检索的key为:1170^3 ≈ 16亿,即只需要3次IO就能检索16亿的key。

如果是varchar等其他字符类型,占用Page字节较大,非叶子节点存储键值会减少,相应可检索的key也减少,树高度就有可能会升高,IO会就多一次,从而导致相对变慢。一般2~4层高度大部分已经够用了。

B+Tree主键索引:

InnoDB中主键索引的叶子节点的数据区域存储的是数据记录,辅助索引存储的是主键值。

B+Tree辅助索引:

Innodb中的主键索引和实际数据时绑定在一起的,也就是说Innodb的一个表一定要有主键索引,如果一个表没有手动建立主键索引,Innodb会查看有没有唯一索引,如果有则选用唯一索引作为主键索引,如果连唯一索引也没有,则会默认建立一个隐藏的主键索引(用户不可见)。另外,Innodb的主键索引要比MyISAM的主键索引查询效率要高(少一次磁盘IO),并且比辅助索引也要高很多。

所以,我们在使用Innodb作为存储引擎时,我们最好:

  • 每个表都创建主键索引
  • 最好是int型作为主键
  • 尽量根据主键查询

MySQL实战知识分享,紧密业务需求,帮助初学者更快熟悉MySQL,更快成长为高级MySQL DBA。

原文发布于微信公众号 - MYSQL轻松学(learnmysql)

原文发表时间:2019-03-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券