索引是什么
维基百科对数据库索引的定义:
数据库索引,是数据库管理系统(DBMS)中一个排序的数据结构,以协助快速查询、更新数据库表中数据。
怎么理解这个定义呢?
首先数据是以文件的形式存放在磁盘上面的,每一行数据都有它的磁盘地址。如果没有索引的话,要从 500 万行数据里面检索一条数据,只能依次遍历这张表的全部数据,直到找到这条数据。
但是有了索引之后,只需要在索引里面去检索这条数据就行了,因为它是一种特殊的专门用来快速检索的数据结构,我们找到数据存放的磁盘地址以后,就可以拿到数据了。
就像我们从一本 500 页的书里面去找特定的一小节的内容,肯定不可能从第一页开始翻。那么这本书有专门的目录,它可能只有几页的内容,它是按页码来组织的,可以根据拼音或者偏旁部首来查找,只要确定内容对应的页码,就能很快地找到我们想要的内容。
索引类型
在 InnoDB 里面,索引类型有三种,普通索引、唯一索引(主键索引是特殊的唯一索引)、全文索引。
- 普通(Normal):也叫非唯一索引,是最普通的索引,没有任何的限制。
- 唯一(Unique):唯一索引要求键值不能重复。另外需要注意的是,主键索引是一种特殊的唯一索引,它还多了一个限制条件,要求键值不能为空。主键索引用 primay key创建。
- 全文(Fulltext):针对比较大的数据,比如我们存放的是消息内容,有几 KB 的数据的这种情况,如果要解决 like 查询效率低的问题,可以创建全文索引。只有文本类型的字段才可以创建全文索引,比如 char、varchar、text。 MyISAM 和 InnoDB 支持全文索引.
create table m3 (
name varchar(50),
fulltext index(name)
);
全文索引的使用:
select * from fulltext_test where match(content) against('这里是要搜索的文本' IN NATURAL LANGUAGE MODE);
索引存储模型推演
二分查找
双十一过去之后,你女朋友跟你玩了一个猜数字的游戏。 猜猜我昨天买了多少钱,给你五次机会。 10000?低了。30000?高了。接下来你会猜多少? 20000。为什么你不猜 11000,也不猜 29000 呢? 其实这个就是二分查找的一种思想,也叫折半查找,每一次,我们都把候选数据缩小了一半。如果数据已经排过序的话,这种方式效率比较高。
所以第一个,我们可以考虑用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高,但是更新数据的时候会出现一个问题,可能要挪动大量的数据(改变 index),所以只适合存储静态的数据。为了支持频繁的修改,比如插入数据,我们需要采用链表。链表的话,如果是单链表,它的查找效率还是不够高。
所以,有没有可以使用二分查找的链表呢?
为了解决这个问题,BST(Binary Search Tree)也就是我们所说的二叉查找树诞生了。
二叉查找树
二叉查找树的特点是什么?
左子树所有的节点都小于父节点,右子树所有的节点都大于父节点。投影到平面以后,就是一个有序的线性表。二叉查找树既能够实现快速查找,又能够实现快速插入。
但是二叉查找树有一个问题: 就是它的查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成O(n)。
什么情况是最坏的情况呢?
还是刚才的这一批数字,如果我们插入的数据刚好是有序的,2、6、11、13、17、22。这个时候我们的二叉查找树变成了什么样了呢?
它会变成链表(我们把这种树叫做“斜树”),这种情况下不能达到加快检索速度的目的,和顺序查找效率是没有区别的。
造成它倾斜的原因是什么呢?
因为左右子树深度差太大,这棵树的左子树根本没有节点——也就是它不够平衡。 所以,我们有没有左右子树深度相差不是那么大,更加平衡的树呢? 这个就是平衡二叉树,叫做 Balanced binary search trees,或者 AVL 树(AVL 是发明这个数据结构的人的名字)。
平衡二叉树(AVL Tree)(左旋、右旋)
AVL Trees (Balanced binary search trees)平衡二叉树的定义:左右子树深度差绝对值不能超过 1。是什么意思呢?比如左子树的深度是 2,右子树的深度只能是 1 或者 3。这个时候我们再按顺序插入 1、2、3、4、5、6,一定是这样,不会变成一棵“斜树”。
那它的平衡是怎么做到的呢?怎么保证左右子树的深度差不能超过 1 呢?
插入 1、2、3。
我们注意看:当我们插入了 1、2 之后,如果按照二叉查找树的定义,3 肯定是要在2 的右边的,这个时候根节点 1 的右节点深度会变成 2,但是左节点的深度是 0,因为它没有子节点,所以就会违反平衡二叉树的定义。 那应该怎么办呢?因为它是右节点下面接一个右节点,右-右型,所以这个时候我们要把 2 提上去,这个操作叫做左旋。
同样的,如果我们插入 7、6、5,这个时候会变成左左型,就会发生右旋操作,把 6提上去。
所以为了保持平衡,AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。
平衡的问题我们解决了,那么平衡二叉树作为索引怎么查询数据?在平衡二叉树中,一个节点,它的大小是一个固定的单位,作为索引应该存储什么内容?
它应该存储三块的内容:
- 第一个是索引的键值。比如我们在 id 上面创建了一个索引,我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。
- 第二个是数据的磁盘地址,因为索引的作用就是去查找数据的存放的地址。
- 第三个,因为是二叉树,它必须还要有左子节点和右子节点的引用,这样我们才能找到下一个节点。比如大于 26 的时候,走右边,到下一个树的节点,继续判断。
如果是这样存储数据的话,我们来看一下会有什么问题。
在分析用 AVL 树存储索引数据之前,我们先来学习一下 InnoDB 的逻辑存储结构。
InnoDB 逻辑存储结构
MySQL 的存储结构分为:表空间、段、簇、页。
表空间 Table Space
上节课讲磁盘结构的时候讲过了,表空间可以看做是 InnoDB 存储引擎逻辑结构的最高层,所有的数据都存放在表空间中。分为:系统表空间、独占表空间、通用表空间、临时表空间、Undo 表空间。
段 Segment
表空间是由各个段组成的,常见的段有数据段、索引段、回滚段等,段是一个逻辑的概念。一个 ibd 文件(独立表空间文件)里面会由很多个段组成。
创建一个索引会创建两个段,一个是索引段:leaf node segment,一个是数据段:non-leaf node segment。索引段管理非叶子节点的数据。数据段管理叶子节点的数据。也就是说,一个表的段数,就是索引的个数乘以 2。
簇 Extent
一个段(Segment)又由很多的簇(也可以叫区)组成,每个区的大小是 1MB(64个连续的页)。
每一个段至少会有一个簇,一个段所管理的空间大小是无限的,可以一直扩展下去,但是扩展的最小单位就是簇。
页 Page
为了高效管理物理空间,对簇进一步细分,就得到了页。簇是由连续的页(Page)组成的空间,一个簇中有 64 个连续的页。 (1MB/16KB=64)。这些页面在物理上和逻辑上都是连续的。
跟大多数数据库一样,InnoDB 也有页的概念(也可以称为块),每个页默认 16KB。页是 InnoDB 存储引擎磁盘管理的最小单位,通过 innodb_page_size 设置。
一个表空间最多拥有 2^32 个页,默认情况下一个页的大小为 16KB,也就是说一个表空间最多存储 64TB 的数据。
注意,文件系统中,也有页的概念。
操作系统和内存打交道,最小的单位是页 Page。文件系统的内存页通常是 4K。
SHOW VARIABLES LIKE 'innodb_page_size';
假设一行数据大小是 1K,那么一个数据页可以放 16 行这样的数据。
举例:一个页放 3 行数据。
往表中插入数据时,如果一个页面已经写完,产生一个新的叶页面。如果一个簇的所有的页面都被用完,会从当前页面所在段新分配一个簇。如果数据不是连续的,往已经写满的页中插入数据,会导致叶页面分裂:
下面我们继续看一下,用 AVL 树存储索引数据,会有什么样的问题。
2.3.2.AVL 树用于存储索引数据
首先,索引的数据,是放在硬盘上的。查看数据和索引的大小:
select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len,CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len from information_schema.TABLES where table_schema='user' and table_name='user_innodb';
当我们用树的结构来存储索引的时候,访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是 16K(16384 字节)。那么,一个树的节点就是 16K 的大小。
如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字节,它远远达不到 16K 的容量,所以访问一个树节点,进行一次 IO 的时候,浪费了大量的空间。
所以如果每个节点存储的数据太少,从索引中找到我们需要的数据,就要访问更多的节点,意味着跟磁盘交互次数就会过多。
如果是机械硬盘时代,每次从磁盘读取数据需要 10ms 左右的寻址时间,交互次数越多,消耗的时间就越多。
比如上面这张图,我们一张表里面有 6 条数据,当我们查询 id=37 的时候,要查询两个子节点,就需要跟磁盘交互 3
次,如果我们有几百万的数据呢?这个时间更加难以估计。
所以我们的解决方案是什么呢?
第一个就是让每个节点存储更多的数据。 第二个,节点上的关键字的数量越多,我们的指针数也越多,也就是意味着可以有更多的分叉(我们把它叫做“路数”)。因为分叉数越多,树的深度就会减少(根节点是 0)。
这样,我们的树是不是从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子?这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路
。
多路平衡查找树(B Tree)(分裂、合并)
Balanced Tree
这个就是我们的多路平衡查找树,叫做 B Tree(B 代表平衡)。跟 AVL 树一样,B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
它有一个特点:分叉数(路数)永远比关键字数多 1。比如我们画的这棵树,每个节点存储两个关键字,那么就会有三个指针指向三个子节点。
B Tree 的查找规则是什么样的呢?
比如我们要在这张表里面查找 15。
- 因为 15 小于 17,走左边。
- 因为 15 大于 12,走右边。
- 在磁盘块 7 里面就找到了 15,只用了 3 次 IO。
这个是不是比 AVL 树效率更高呢?那 B Tree 又是怎么实现一个节点存储多个关键字,还保持平衡的呢?跟 AVL 树有什么区别?
比如 Max Degree(路数)是 3 的时候,我们插入数据 1、2、3,在插入 3 的时候,本来应该在第一个磁盘块,但是如果一个节点有三个关键字的时候,意味着有 4 个指针,子节点会变成 4 路,所以这个时候必须进行分裂。把中间的数据 2 提上去,把 1 和 3 变成 2 的子节点。
如果删除节点,会有相反的合并的操作。注意这里是分裂和合并,跟 AVL 树的左旋和右旋是不一样的。我们继续插入 4 和 5,B Tree 又会出现分裂和合并的操作。 从这个里面我们也能看到,在更新索引的时候会有大量的索引的结构的调整,所以解释了为什么我们不要在频繁更新的列上建索引,或者为什么不要更新主键。
节点的分裂和合并,其实就是 InnoDB 页的分裂和合并。
B+树(加强版多路平衡查找树)
B Tree 的效率已经很高了,为什么 MySQL 还要对 B Tree 进行改良,最终使用了B+Tree 呢?
总体上来说,这个 B 树的改良版本解决的问题比 B Tree 更全面。我们来看一下 InnoDB 里面的 B+树的存储结构:
MySQL 中的 B+Tree 有几个特点:
举个例子:假设一条记录是 1K,一个叶子节点(一页)可以存储 16 条记录。非叶子节点可以存储多少个指针?
假设索引字段是 bigint 类型,长度为 8 字节。指针大小在 InnoDB 源码中设置为6 字节,这样一共 14 字节。非叶子节点(一页)可以存储 16384/14=1170 个这样的单元(键值+指针),代表有 1170 个指针。树 深 度 为 2 的 时 候 , 有 1170^2 个 叶 子 节 点 , 可 以 存 储 的 数 据 为1170117016=21902400。
在查找数据时一次页的查找代表一次 IO,也就是说,一张 2000 万左右的表,查询数据最多需要访问 3 次磁盘。所以在 InnoDB 中 B+ 树深度一般为 1-3 层,它就能满足千万级的数据存储。
我们来看一下 B+Tree 的数据搜寻过程:
总结一下,InnoDB 中的 B+Tree 的特点: