专栏首页MYSQL轻松学MySQL Index 之 B+Tree数据结构

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),作者:MYSQL轻松学

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试中有哪些经典的数据库问题?

    1、如果我们定义了主键(PRIMARY KEY),那么InnoDB会选择主键作为聚集索引、如果没有显式定义主键,则InnoDB会选择第一个不包含有NULL值的唯...

    MySQL轻松学
  • Mysql聚集索引和非聚集索引

    首先要明确一个概念,在聚集索引的世界里索引就是数据,在最后的叶子索引键保存着对应的数据行。 举个例子: 表TestNonclusteredIndex ID ...

    MySQL轻松学
  • MYSQL5.6优化器的一个新特性MMR

    一、什么是MRR MMR全称是Multi-Range Read,是MYSQL5.6优化器的一个新特性,在MariaDB5.5也有这个特性。优化的功能在使用二级索...

    MySQL轻松学
  • geotrellis使用(五)使用scala操作Accumulo

        要想搞明白Geotrellis的数据处理情况,首先要弄清楚数据的存放,Geotrellis将数据存放在Accumulo中。     Accumulo是一...

    魏守峰
  • 我的简单设计价值观

    很多时候,我们习惯把简单跟容易理解为是一个意思,比如:这个问题好简单(复杂),另一层含义是:解决这个问题很容易(困难)?这个时候简单跟容易是一个意思。再比如说:...

    袁慎建@ThoughtWorks
  • 记一次带层级结构列表数据计算性能优化

      最近,负责一个类财务软件数据计算的性能优化工作。先说下=这项目的情况,一套表格,几十张表格,每张表格数据都是层级结构的,通过序号确定父子级关系,如1,1.1...

    guokun
  • Flask 入门一( flask 框架和 flask-script 库)

    今天小婷儿给大家分享的是Flask 入门一( flask 框架和 flask-script 库)。

    小麦苗DBA宝典
  • 2019年常见ElasticSearch面试题解析(上)

    ElasticSearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎,基于RESTful web接口。Elasticsear...

    程序员追风
  • 2018全国大学生软件测试大赛-安恒杯Web测试大赛write up

    这里的知识点是当代码中存在$_REQUEST['user_id']里面类似的参数的时候,使用" "、"["、"+"、"."这样的符号的时候回自动转化成"_"从而...

    安恒网络空间安全讲武堂
  • 快速学习ES6新特性-map和reduce

    reduce() :接收一个函数(必须)和一个初始值(可选),该函数接收两个参数:

    cwl_java

扫码关注云+社区

领取腾讯云代金券