专栏首页兜兜毛毛MySQL 索引(3)

MySQL 索引(3)

什么是索引?

索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。

比如想从字典中查询某一个字,我们可以通过偏旁、或者拼音来快速定位到要找的页码,这种方式也可以被理解为一种索引。

Mysql常用的索引类型

类型

说明

Normal(普通)

普通索引,没任何限制。

Unique(唯一)

唯一索引要求健值不能重复。

Fulltext(全文)

针对比较大的数据,如商品详情,可以解决like查询效率低的问题。

索引的存储模型推演

索引是一种数据结构,那它到底是一种什么数据结构,才能实现数据的高效检索呢?

1. 二分查找

在给定一个有序数组中,如何以最快的方式找出给定的值? 有一点开发经验的第一个一定会想到使用二分查找方法进行查找。 比如有1到100的有序数组。另一个在中间想一个数,你猜的时候会告诉你高了,还是低了。

  • 50? 高了
  • 25?低了
  • 37? 以上就是二分查找的一种思想,我们每次说一个数,就可以把结果范围缩小一半。如果数据是有序的话,这种方式效率比较高。

有序数据的等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题,可能要挪动大量的数据(改变Index),所以只适合静态数据。

为了支持频繁的修改,如插入,我们可以采用链表,但他的查找效率不够高。

所以有没有可以使用二分查找的链表呢?

2.二叉查找树(BST Binary Search Tree)

左子树所有的节点都小于父节点,右子树所有的节点都大于父节点。投影到平面以后,就是一个有序的线性表。

二叉树的特点:

左子树节点 < 父节点
右子树节点 > 父节点

二叉查找树既能够实现快速查找,又能够实现快速插入。

但是二叉查找树有一个问题:

就是它的查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成O(n)。

什么情况是最坏的情况呢?

可以使用下边地址模拟:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

用上边的数据按6、13、23、30、34、45有序输入,就会发现这时候二叉树变成了一个《斜树》,这种情况下和顺序查找效率是没区别的。

因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。

3. 平衡二叉树(AVL Tree)

平衡二叉树的定义:左右子树深度差绝对值不能超过1。

什么意思呢?比如左子树的深度是2,右子树的深度只能是1或者3。

还用上边的数据按6、13、23、30、34、45有序输入,一定不会再变成一棵《斜树》。

平衡的问题我们解决了,那么平衡二叉树作为索引怎么查询数据?

在平衡二叉树中,一个节点,它的大小是一个固定的单位,作为索引应该存储什么内容?

它应该存储三块的内容:

  1. 是索引的键值。比如我们在id上面创建了一个索引,我在用whereid=1的条件查询的时候就会找到索引里面的id的这个键值。
  2. 是数据的磁盘地址,因为索引的作用就是去查找数据的存放的地址。
  3. 因为是二叉树,它必须还要有左子节点和右子节点的引用,这样我们才能找到下一个节点。比如大于26的时候,走右边,到下一个树的节点,继续判断。

如果是这样存储数据的话,我们来看一下会有什么问题。

在分析用AVL树存储索引数据之前,我们先来学习一下InnoDB的逻辑存储结构。

InnoDB 逻辑存储结构

MySQL的存储结构分为5级:表空间、段、簇、页、行。

表空间 TableSpace

上一章讲磁盘结构的时候讲过了,表空间可以看做是InnoDB存储引擎逻辑结构的最高层,所有的数据都存放在表空间中。分为:系统表空间、独占表空间、通用表空间、临时表空间、Undo表空间。

段 Segment

表空间是由各个段组成的,常见的段有数据段、索引段、回滚段等,段是一个逻辑的概念。一个ibd文件(独立表空间文件)里面会由很多个段组成。

创建一个索引会创建两个段,一个是索引段:leaf node segment,一个是数据段:non-leaf node segment。索引段管理非叶子节点的数据。数据段管理叶子节点的数据。也就是说,一个表的段数,就是索引的个数乘以2。

簇 Extent

一个段(Segment)又由很多的簇(也可以叫区)组成,每个区的大小是1MB(64个连续的页)。

每一个段至少会有一个簇,一个段所管理的空间大小是无限的,可以一直扩展下去,但是扩展的最小单位就是簇。

页 Page

https://dev.mysql.com/doc/refman/5.7/en/innodb-row-format.html

为了高效管理物理空间,对簇进一步细分,就得到了页。簇是由连续的页(Page)组成的空间,一个簇中有64个连续的页。(1MB/16KB=64)。这些页面在物理上和逻辑上都是连续的。

跟大多数数据库一样,InnoDB也有页的概念(也可以称为块),每个页默认16KB。页是InnoDB存储引擎磁盘管理的最小单位,通过innodb_page_size设置。

一个表空间最多拥有2^32个页,默认情况下一个页的大小为16KB,也就是说一个表空间最多存储64TB的数据。

注意,文件系统中,也有页的概念。操作系统和内存打交道,最小的单位是页Page。文件系统的内存页通常是4K。

假设一行数据大小是1K,那么一个数据页可以放16行这样的数据。

往表中插入数据时,如果一个页面已经写完,产生一个新的叶页面。如果一个簇的所有的页面都被用完,会从当前页面所在段新分配一个簇。

如果数据不是连续的,往已经写满的页中插入数据,会导致叶页面分裂:

行 Row

InnoDB存储引擎是面向行的(row-oriented),也就是说数据的存放按行进行存放。

Antelope[ˈæntɪləʊp](羚羊)是InnoDB内置的文件格式,有两种行格式:

REDUNDANT[rɪˈdʌndənt] Row Format COMPACT Row Format(5.6默认)

Barracuda[ˌbærəˈkjuːdə](梭子鱼)是InnoDB Plugin支持的文件格式,新增了两种行格式:

文件格式

行格式

描述

Antelope(Innodb-base)

ROW_FORMAT=COMPACT

Compact和redumdant的区别在就是在于首部的存存内容区别。compact的存储格式为首部为一个非NULL的变长字段长度列表。

--

ROW_FORMAT=REDUNDANT

redundant的存储格式为首部是一个字段长度偏移列表(每个字段占用的字节长度及其相应的位移)。在Antelope中对于变长字段,低于768字节的,不会进行overflowpage存储,某些情况下会减少结果集IO.

Barracuda (innodb-plugin)

ROW_FORMAT=DYNAMIC

这两者主要是功能上的区别功能上的。另外在行里的变长字段和Antelope的区别是只存20个字节,其它的overflowpage存储。

--

ROW_FORMAT=COMPRESSED

另外这两都需要开启innodb_file_per_table=1

innodb_file_format在配置文件中指定;

row_format则在创建数据表时指定。

# 在创建表的时候可以指定行格式。
CREATE TABLE tableName1
( id int PRIMARYKEY)
ROW_FORMAT = COMPRESSED
KEY_BLOCK_SIZE = 8;

# 查看表的行格式
show table status like 'tableName1';
AVL树用于存储索引数据

当我们用树的结构来存储索引的时候,访问一个节点就要跟磁盘之间发生一次IO。InnoDB操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是16K(16384字节)。

那么,一个树的节点就是16K的大小。

如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到16K的容量,所以访问一个树节点,进行一次IO的时候,浪费了大量的空间。

所以如果每个节点存储的数据太少,从索引中找到我们需要的数据,就要访问更多的节点,意味着跟磁盘交互次数就会过多。

如果是机械硬盘时代,每次从磁盘读取数据需要10ms左右的寻址时间,交互次数越多,消耗的时间就越多。

比如上面这张图,我们一张表里面有6条数据,当我们查询id=23的时候,要查询两个子节点,就需要跟磁盘交互3次,如果我们有几百万的数据呢?这个时间更加难以估计。

所以我们的解决方案是什么呢?

第一个就是让每个节点存储更多的数据。

第二个,节点上的关键字的数量越多,我们的指针数也越多,也就是意味着可以有更多的分叉(我们把它叫做“路数”)。

因为分叉数越多,树的深度就会减少(根节点是0)。

这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子?

这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。

4. 多路平衡查找树(BTree)(分裂、合并)

Balanced Tree这个就是我们的多路平衡查找树,叫做BTree(B代表平衡)。

跟AVL树一样,B树在枝节点和叶子节点存储键值、数据地址、节点引用。

它有一个特点:分叉数(路数)永远比关键字数多1。比如我们画的这棵树,每个节点存储两个关键字,那么就会有三个指针指向三个子节点。

B Tree的查找规则是什么样的呢?

比如我们要在这张表里面查找15。
因为15小于17,走左边。
因为15大于12,走右边。
在磁盘块7里面就找到了15,只用了<3>次IO。

这个是不是比AVL树效率更高呢?那BTree又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟AVL树有什么区别?

https://www.cs.usfca.edu/~galles/visualization/BTree.html

比如MaxDegree(路数)是3的时候,我们插入数据1、2、3,在插入3的时候,本来应该在第一个磁盘块,但是如果一个节点有三个关键字的时候,意味着有4个指针,子节点会变成4路,所以这个时候必须进行分裂。把中间的数据2提上去,把1和3变成2的子节点。

从这个里面我们也能看到,在更新索引的时候会有大量的索引的结构的调整,所以解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。

节点的分裂和合并,其实就是InnoDB页的分裂和合并。

5. B+树(加强版多路平衡查找树)

BTree的效率已经很高了,为什么MySQL还要对BTree进行改良,最终使用了B+Tree呢?

总体上来说,这个B树的改良版本解决的问题比BTree更全面。

我们来看一下InnoDB里面的B+树的存储结构:

MySQL中的B+Tree有几个特点:

1、它的关键字的数量是跟路数相等的

2、B+Tree的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。搜索到关键字不会直接返回,会到最后一层的叶子节点。比如我们搜索id=28,虽然在第一层直接命中了,但是全部的数据在叶子节点上面,所以我还要继续往下搜索,一直到叶子节点。

举个例子:假设一条记录是1K,一个叶子节点(一页)可以存储16条记录。非叶子节点可以存储多少个指针?

假设索引字段是bigint类型,长度为8字节。指针大小在InnoDB源码中设置为6字节,这样一共14字节。非叶子节点(一页)可以存储16384/14=1170个这样的单元(键值+指针),代表有1170个指针。

树深度为2的时候,有1170^2个叶子节点,可以存储的数据为1170117016=21902400。

在查找数据时一次页的查找代表一次IO,也就是说,一张2000万左右的表,查询数据最多需要访问3次磁盘。

所以在InnoDB中B+树深度一般为1-3层,它就能满足千万级的数据存储。

3、B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。

4、它是根据左闭右开的区间[)来检索数据。

索引的创建

1、在用于where判断order排序和join的(on)字段上创建索引

2、索引的个数不要过多。——浪费空间,更新变慢。

3、区分度低的字段,例如性别,不要建索引。——离散度太低,导致扫描行数过多。

4、频繁更新的值,不要作为主键或者索引。——页分裂

5、组合索引把散列性高(区分度高)的值放在前面。

6、创建复合索引,而不是修改单列索引。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 集群(11)

    Redis本身的QPS已经很高了,但是如果在一些并发量非常高的情况下,性能还是会受到影响。这个时候我们希望有更多的Redis服务来完成工作。

    兜兜毛毛
  • Redis ZSet (5)

    ZSet集合基本与Set相同,只是多了一个数值类型属性score,score相同时,按照Key的ASC码排序。

    兜兜毛毛
  • 在MySQL里将中文转换成拼音

    兜兜毛毛
  • 深入理解MySQL索引底层数据结构与算法

    在开始讲这一小节之前,我们先来看一下在数据库没有加索引的情况下,SQL中的where字句是如何查找目标记录的。

    用户6182664
  • 一文带你深入理解Mysql索引底层数据结构与算法

    首先看一下,在数据库没有加索引的情况下,SQL中的where语句是如何查找目标记录的,首先看到下图的Col2字段,如果我们要查找where col2 = 89的...

    黎明大大
  • MySQL 索引

      我们用一个例子来逐渐引出啥是索引。话说大老板东哥有一天想体验一下快递小哥的生活,就去自家快递公司准备干活了,一进仓库看到一地的快递,兴冲冲的就问旁边的快递小...

    Demo_Null
  • 数据结构与算法-跳表

    在学习二分查找时,我们知道二分查找需要依赖数组的随机访问的特性进行查找,而链表不具有随访问的特性,因此不能使用传统上的二分查找方法了。为了使得链表支持类...

    用户3470542
  • 不准犹豫!再有人问你为什么MySQL用B+树做索引,就把这篇文章发给她

    索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从...

    帅地
  • B树?这篇文章彻底看懂了!

    索引,相信大多数人已经相当熟悉了,很多人都知道 MySQL 的索引主要以 B+ 树为主,但是要问到为什么用 B+ 树,恐怕很少有人能把前因后果讲述完整。本文就来...

    程序员追风
  • 再有人问你为什么MySQL用B+树做索引,就把这篇文章发给她

    索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从...

    Java3y

扫码关注云+社区

领取腾讯云代金券