引言
内容为慕课网的《高并发 高性能 高可用 MySQL 实战》视频的学习笔记内容和个人整理扩展之后的笔记，这一节的内容是对于InnoDb的存储结构进阶了解，同时介绍为什么会使用B+索引作为最终数据结构，但是实际上InnoDb在具体实现中也并没有完全遵循B+的格式，而是在内部做了很多“手脚”，这也是所谓理论和实践之间的差异。
如果内容比较难，可以跟随《Mysql是怎么样运行》个人读书笔记专栏补补课，个人也在学习和同步更新中。
索引组织表
InnoDb 的所有表都是索引组织表，索引组织表有如下的定义：
不是一种“组织表”，而是由“索引”组织的表，索引即数据数据即索引，InnoDb中表默认都会主键顺序存放，同时按照一定的规则排序，默认的索引组织形式被称为聚簇索引。
什么是索引？
索引可以简单理解为目录，类似于我们书中的目录页，帮我们快速定位具体的内容，对于数据库某一列或者多列进行预排序的数据结构，注意这是一种数据结构目的是为了加快数组的搜索速度。
但是索引也有问题，那就是目录本身也需要占用存储空间并且随着数据的膨胀而膨胀，同时如果索引使用的不恰当也会出现问题，比如如果我们的目录索引的内容全都是一模一样的会出现“索引失效”问题，此时索引效果大打折扣，不如直接搜索数据。
主键定义和主键索引
在Mysql的Inndb存储引擎中，使用的主键索引也被称为聚簇索引：
InnoDb 的存储引擎表中每张表必须有一个主键，表中有一个非空唯一索引即为主键。如果存在多个非空唯一索引并且没有定义主键，选择第一个定义的索引，若所有条件不满足则InnoDb在数据行中自动创建一个6个字节的指针隐藏列作为主键，并且这个主键内部是自增的使得记录可以按照顺序进行存储。
下面用视频中的案例举例讨论的下面这个表主键是什么？
从上面的截图可以看到，字段a没有定义唯一索引，虽然它是非空的但是并不是唯一的所以不是主键，b虽然是最先定义的，但是他不是非空所以也不能作为索引，而d和 c虽然都是唯一索引并且都是非空列，根据多个非空索引取第一个定义索引为主键的规则，最终主键为字段d。
B+树索引
B+树的索引结构是InnoDb的基础结构，下面是传统的B+树的结构：
- Btree 使用B+树作为索引的数据结构。
- B+树的高度为2-4层，查找数据十分快。
- B+树索引将非叶子节点所谓索引节点，叶子节点为数据节点，数据节点之间用链表串联实现优化范围查询。
Inndo的B+树和传统B+树的区别如下：
- InnoDb底层参考的是b+ 树，但是其实不完全相同，节点被称之为数据页和索引页，但是实际上索引页数据页除了数据类型不同基本一致，也就是索引即数据，数据即索引，索引它分为聚簇索引和辅助索引，聚簇索引最大特点是存放键是主键ID，而主键ID根据一定的规则生成或者在建表的时候指定，但是一定会有一个主键索引，也就说一个表一定存在主键。而辅助索引使用的是主键为索引字段的值，数值存放的是索引主键。
- 同层的数据页之间使用的是双向链表，索引页也是使用双向链表，这和B+树的数据结构是不一样的，传统B+ 树只在最底层的叶子节点为链表的设计。
聚簇索引
聚簇索引指的是根据表的主键构建一个B+ 树。叶子节点直接存放行数据而不是放指针，但是实际上叶子节点本身也是数据页只不过存放的是指针而已。
下面的案例图仅仅为最粗糙的角度观察mysql的数据页设计，实际内容要远比这张图复杂很多：
聚簇索引的特点
- 非叶子节点存储的是索引，叶子节点则为数据，从左到右排序，在页分裂的时候，会把主键较大的值移动到对应的数据页。
- 索引页之间使用链表进行连接，而叶子节点实际的数据存储区域，统一使用链条表进行串联。所以可以发现除开最顶层，所有的层级页和页之间是由链表之间链接的。
- 每一个数据页包含infimum数据行代表当前数据页的第一个节点也就是最小值，supermum代表最后一个节点也就是最大值，这两个“行记录”是Mysql设计者的一个小把戏，目的是方便数据的查找和不同数据页之间的串联，也就是说每一个数据页默认至少有两个“虚拟”数据行。
- 所有的数据页号会组成一个页目录，按照最大数据的数据页号进行排序，页目录里面从小到大存放了主键的id值，通过值找到对应的数据页内容，用于快速定位数据所在的数据页。
- Innodb 默认为主键索引也就是聚簇索引。
为什么要使用从大到小的顺序进行排序？
其实主要是为了使用二分查找方法快速定位和查找数据页，提高查找的效率。注意由于早期Mysql版本中的索引设计只能按照升序的方式进行排列，导致聚簇索引多数为升序的索引，在8.0的版本中得到优化。
辅助索引
辅助索引的存在形式：
- 和主键索引的设计一样，但是key存放的是索引字段的值，值是主键值。
- 辅助索引根据建立的索引除联合索引的情况外均为有几个索引建立几颗B+ 树。
- 辅助索引相当于一颗新的B+ 树。
主键索引：
- 主键索引也叫聚簇索引，由于底层使用了B+ 树的设计结构，所以Mysql必定有主键并且以主键作为索引的形式。
- 主键索引指的是键为主键，值为数据一种 索引形式。
- 一旦创建表则系统默认会存在一颗以主键索引的B+ 树。
回表是什么？
当辅助索引进行查询的时候由于查询的结果为主键的值，所以需要根据主键的值再去聚簇索引根据二分法查找一遍，这时候等于需要再查一遍聚簇索引，本质上是查了两次B+ 树，所以叫回表。
下面的示意图是一次回表操作：
假设我们需要搜索值为5的数据，首先会在二级索引通过二分遍历“槽”的形式找到具体所在的数据行，这个数据行保存索引值之外还存储了主键的值，所以这里需要拿到主键的值回到聚簇索引中找到实际存储的行记录。
但是如果查找条件和查找列都为索引值实际上会使用“覆盖索引”的查找方式，不需要回表操作。
索引算法
对于刚刚接触B+树的同学看到这些数据结构可能会懵圈，同时也不清楚为什么要设计这么个复杂的玩意，所以在课程中引入了各种数据结构来介绍为什么最终选择了B+树的结构，下面我们来简单对比各种常见的数据结构来了解为什么最后选择了B+ 树这种数据结构。
对于一些常见的算法可以阅读下面的网站了解：Data Structure Visualization (usfca.edu)。
哈希表
哈希表的数据结构十分简单，只包含简单的键值对，用哈希函数给索引列计算一个哈希值存储，哈希表最典型的索引应用类型是哈希索引，通过对于索引列的总列计算一个哈希函数进行存储。
哈希表缺点：
哈希表最大的问题在于key冲突，因为如果存在key冲突，那么此时索引会退化为顺序的全表遍历，或者说拉出一个链表存储冲突哈希key进行遍历，并且哈希索引最为适用的等值查询实际在使用过程中并不是十分频繁，更多的时候会使用范围或者模糊搜索，这时候哈希表的数据结构是很难发挥作用的。
- 哈希表不适用于范围查找和模糊搜索。
- 哈希冲突会退化为顺序遍历查询。
线性结构
线性结构指的是经典数组，包括链表，数组和堆栈结构，比如数组的查询效率是O(n)，并且查找的性能是O(1)，看起来是对于设计数据库比较合适。
特点：
- 时间复杂度
O(n)。 - 需要从第一个开始做一次遍历线性查找，查找的效率是
O(1)。 - 数组的特点是查找快，更新慢，而链表的特点是更新快，查找稍慢。
不适合作为数据库的缺点：
对于任意的线性结构来说的查找，更新，删除的速度似乎很不错，但是顺序数组的插入速度不能接受，尤其是在数组中间插入的时候，需要拷贝数组向后挪位置，而链条的查找速度不能接受并且不利于磁盘存储，如果数据量很大的情况下开销庞大，显然都是不适合的。
二分查找：二分查找对于线性数组结构来说是非常常用的方式，有序数组在等值查询和范围查询场景中的性能就都非常优秀。
二分查找演示图：www.cs.usfca.edu/~galles/vis…
- 时间复杂度（O(logn)），每一次查找都是上一次的一半。
- 使用数组的中点作为比较对象。
- 根据中点数据大小，选择一半数据作为新数列查找。
- 每次可以查找的数据量为一半。
不足点：二分查找虽然在查询上提升一个量级，但是依然没有避免插入的问题。
二叉树
既然线性结构有限制，那么逻辑结构是否可行？所以我们可以思考如果用二叉树如何处理。
- 时间复杂度是O(logN)。
- 搜索效率的速度取决于树的高度。
- 遍历方式，分为前序遍历，中序遍历，后序遍历。
- 如果所有的节点往一侧添加，可能退化为线性查找。
不适合作为数据库的缺点：
插入和删除需要耗费一定的性能，并且为了节点的稳定，需要使用左旋或者右旋的操作，维持二叉树的平衡，所以后续拓展出平衡二叉树和红黑树。
平衡二叉树和红黑树
平衡二叉树针对二叉树引入左旋和右旋的操作维持平衡，平衡二叉树的定义是：左右两个子树的高度差不能超过 1，左右两边相对平衡，因此称之为平衡二叉树。而红黑树s
- AVL 树，通过左旋和右旋的操作将节点进行上浮或者下沉。
- AVL树保证不会退化为线性查找。
不适合作为数据库的缺点：
1. 虽然可以保证查询的性能不会退化，但是对于树的左旋和右旋的操作十分耗费性能，在存储数据的时候会出现长时间等待的情况，同时还是会发现这样存储的效率是十分低的，同时磁盘的利用率十分低。
2. 另外从数据结构图发现还有一个十分明显的缺点，那就是一个节点只能有两个子节点，如果插入大量节点会导致树的高度不断膨胀，即使可以平衡操作，对于插入的操作而言还是十分耗费性能的。
B 树
数据结构演示图：www.cs.usfca.edu/~galles/vis…
既然二叉树只有两个节点，那么我们调整结构，让每一层的节点内容增多，并让树控制在2-4层。同时可以包含多个子节点，这样即可极大提高存储效率，同时这种紧凑的结构也方便磁盘的顺序扫描。
- 线性数据结构和树结构的结合。
- 通过多数据节点大大降低树的高度。
- 不需要旋转就可以保证树的平衡
缺点：
但是很可惜B树有一个十分致命的缺陷，那就是不适合作为范围查找，如果我们想跨越多个范围进行查询，那么需要从根节点遍历一整颗树多次，我们知道范围查询的常见是非常常见的，这样的性能开销对于数据库来说显然不实际。
B+树
数据结构演示图：www.cs.usfca.edu/~galles/vis…
B+树是对于B 树的一种优化和变种，其实可以发现就是在线性结构和逻辑结构的兼容，最终在B树的基础上，所有的数据存在叶子节点，而索引节点放在非叶子节点，最终这样的接口。
特点：
- B+树是B树发展过来的一种数据结构
- B+树所有数据都在叶子节点。
- B+树所有数据最终形成了一个线性表。
