MySQL索引数据模型推演
二分查找
双十一过去之后，你女朋友跟你玩了一个猜数字的游戏。(假设程序员 new 了一个会购物的女朋友出来) 猜猜我昨天买了多少钱，给你五次机会。 10000？低了。30000？高了。 接下来你会猜多少？ 20000。为什么你不猜 11000，也不猜 29000 呢？
其实这个就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。
所以第一个，我们可以考虑用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。
为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。
那么，有没有可以使用二分查找的链表呢？
为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生了。
二叉查找树
二叉查找树的特点是什么？ 左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。
二叉查找树既能够实现快速查找，又能够实现快速插入。
- 但是二叉查找树有一个问题：
它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。
- 什么情况是最坏的情况呢？
我们打开这样一个网站来看一下，这里面有各种各样的数据结构的动态演示，包括 BST 二叉查找树： www.cs.usfca.edu/~galles/vis… 还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、6、11、13、17、 22。 这个时候我们的二叉查找树变成了什么样了呢？
它会变成链表（这种树也叫做“斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。
- 造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
- 所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？
这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树（AVL 是发明这个数据结构的人的名字）。
平衡二叉树
AVL Trees (Balanced binary search trees) 平衡二叉树的定义：
左右子树深度差绝对值不能超过 1。
- 是什么意思呢？
比如左子树的深度是 2，右子树的深度只能是 1 或者 3。 这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。
- 那它的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？
www.cs.usfca.edu/~galles/vis… 插入 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 的逻辑存储结构
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 = 'gupao' 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 有几个特点：
- 它的关键字的数量是跟路数相等的；
- B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。搜索 到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一 层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶 子节点。 举个例子：假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。非叶 子节点可以存储多少个指针？ 假设索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。非叶子节点（一页）可以存储 16384 / 14 = 1170 个这样的 单元（键值+指针），代表有 1170 个指针。 树深度为 2 的时候， 有 1170^2 个叶子节点 ，可以存储的数据为 1170 * 1170 * 16 = 21902400。 在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询数据最多需要访问 3 次磁盘。 所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。
- B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数 据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。
- 它是根据左闭右开的区间 [ )来检索数据。
我们来看一下 B+Tree 的数据搜寻过程：
1）比如我们要查找 28，在根节点就找到了键值，但是因为它不是页子节点，所以会继续往下搜寻，28 是[28,66)的左闭右开的区间的临界值，所以会走中间的子节点，然后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后在叶子节点上找到了需要的数据。
2）第二个，如果是范围查询，比如要查询从 22 到 60 的数据，当找到 22 之后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）。
总结一下，InnoDB 中的 B+Tree 的特点：
- 它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
- 扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）
- B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
- 排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
- 效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）
为什么不用红黑树？
红黑树也是 BST 树，但是不是严格平衡的。
必须满足 5 个约束：
- 节点分为红色或者黑色。
- 根节点必须是黑色的。
- 叶子节点都是黑色的 NULL 节点。
- 红色节点的两个子节点都是黑色（不允许两个相邻的红色节点）。
- 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。
插入：60、56、68、45、64、58、72、43、49
基于以上规则，可以推导出：
从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的 2 倍。
- 为什么不用红黑树？
- 只有两路；
- 不够平衡。
- 红黑树一般只放在内存里面用。例如 Java 的 TreeMap。
索引方式：真的是用的 B+Tree 吗？
在 Navicat 的工具中，创建索引，索引方式有两种，Hash 和 B Tree。
HASH：以 KV 的形式检索数据，也就是说，它会根据索引字段生成哈希码和指针，指针指向数据。
- 哈希索引有什么特点呢？
- 它的时间复杂度是 O(1)，查询速度比较快。因为哈希索引里面的数据不是按顺序存储的，所以不能用于排序。
- 我们在查询数据的时候要根据键值计算哈希码，所以它只能支持等值查询（= IN），不支持范围查询（> < >= <= between and）。
- 另外一个就是如果字段重复值很多的时候，会出现大量的哈希冲突（采用拉链法解决），效率会降低。
- 问题： InnoDB 可以在客户端创建一个索引，使用哈希索引吗？
我们先到官网看看介绍： dev.mysql.com/doc/refman/… InnoDB utilizes hash indexes internally for its Adaptive Hash Index feature 直接翻译过来就是：InnoDB 内部使用哈希索引来实现自适应哈希索引特性。 这句话的意思是 InnoDB 只支持显式创建 B+Tree 索引，对于一些热点数据页， InnoDB 会自动建立自适应 Hash 索引，也就是在 B+Tree 索引基础上建立 Hash 索引，这个过程对于客户端是不可控制的，隐式的。 我们在 Navicat 工具里面选择索引方法是哈希，但是它创建的还是 B+Tree 索引，这个不是我们可以手动控制的。 在 buffer pool 里面有一块区域是 Adaptive Hash Index 自适应哈希索引，就是指这个。
这个开关默认是 ON：
show variables like 'innodb_adaptive_hash_index'; 复制代码
从存储引擎的运行信息中可以看到：
show engine innodb status\G 复制代码
---------------------- BUFFER POOL AND MEMORY ---------------------- ------------------------------------- INSERT BUFFER AND ADAPTIVE HASH INDEX ------------------------------------- 复制代码
因为 B Tree 和 B+Tree 的特性，它们广泛地用在文件系统和数据库中，例如Windows 的 HPFS 文件系统，Oracel、MySQL、SQLServer 数据库。
B+Tree落地形式
MySQL 架构
通过上节课我们知道，MySQL 是一个支持插件式存储引擎的数据库。在 MySQL 里面，每个表在创建的时候都可以指定它所使用的存储引擎。
这里我们主要关注一下最常用的两个存储引擎，MyISAM 和 InnoDB 的索引的实现。
MySQL 数据存储文件
首先，MySQL 的数据都是文件的形式存放在磁盘中的，我们可以找到这个数据目录的地址。在 MySQL 中有这么一个参数，我们来看一下：
show VARIABLES LIKE 'datadir'; 复制代码
每个数据库有一个目录，我们新建了一个叫做 checkit 的数据库，那么这里就有一个checkit 的文件夹。
这个数据库里面我们又建了 5 张表：archive、innodb、memory、myisam、csv。
我们进入 checkit 的目录，发现这里面有一些跟我们创建的表名对应的文件。
在这里我们能看到，每张 InnoDB 的表有两个文件（.frm 和.ibd），MyISAM 的表有三个文件（.frm、.MYD、.MYI）。
有一个是相同的文件，.frm。
.frm 是 MySQL 里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成。
我们主要看一下其他两个文件是怎么实现 MySQL 不同的存储引擎的索引的。
在 MyISAM 里面，另外有两个文件：
一个是.MYD 文件，D 代表 Data，是 MyISAM 的数据文件，存放数据记录，比如我们的 user_myisam 表的所有的表数据。
一个是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我们在 id 字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。
也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。
那我们怎么根据索引找到数据呢？
MyISAM 的 B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。
这里是主键索引，如果是辅助索引，有什么不一样呢？
在 MyISAM 里面，辅助索引也在这个.MYI 文件里面。
辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件
里面找到磁盘地址，然后到数据文件里面获取数据。
再看看 innodb：
InnoDB 只有一个文件（.ibd 文件），那索引放在哪里呢？
在 InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文件是同一个文件，都在.ibd 文件里面。
在 InnoDB 的主键索引的叶子节点上，它直接存储了我们的数据。
