存储引擎和索引
前言
关于 MySQL 的学习着实有些混乱，虽然才到学习笔记二，但学习笔记四都已经写完了，其他写一点，可以说是东一榔头西一棒槌；写出的东西也不忍直视，省略了很多细节，还基本上都是到处搬运的，可即便是搬运，也都绞尽脑汁了。网上的知识大多都模糊不清，甚至还错误百出，为了辨别对错还查阅不少资料，那些书籍真是晦涩难懂，一顿操作下来，着实无力再细细打磨学习笔记阅读的流畅度了。
写这么多前言，其实就是为了叠 buff，如果大家看到错误，或有些该写的内容没有写，或者有什么建议，麻烦评论告知一下，我会虚心改进的。
索引
不知道多少人像笔者一样，一看到索引就会想到编号，像一张表内的学号、身份证号和id号等等，这其实是被索引的表现形式迷惑了。比方说，我们通过学号，就能找到对应学生的信息：
- 我们都知道，整个学校的学生信息内存肯定放不下，是以文件的形式存在磁盘里。
- 要查信息，就得先从磁盘取出来，取出来该怎么存？简单点，我们用数组存，假设学号是连续的，让其和数组下标一一对应存入。（这就建立了索引，且索引的键是学号，值是学生信息）
- 然后怎么查？通过学号计算出对应的数组下标，直接找到对应的数组元素，就查到了。（这是索引的检索过程）
总而言之，索引是一种数据结构，是帮助 MySQL 高效获取数据的数据结构，一般存储在磁盘的文件中，它是占用物理空间的。
索引分类
从功能逻辑上说，索引主要有 4 种，分别是普通索引、唯⼀索引、主键索引和全文索引。
- 普通索引：最基本的索引，它没有任何限制
CREATE TABLE `user` ( `id` int(11) unsigned NOT NULL AUTO_INCREMENT, `name` varchar(64) DEFAULT NULL, PRIMARY KEY (`id`), KEY `name` (`name`) --普通索引 );
- 唯一索引：索引列的值必须唯一，且不能为空，如果是组合索引，则列值的组合必须唯一。
CREATE TABLE `user` ( `id` int(11) unsigned NOT NULL AUTO_INCREMENT, `name` varchar(64) DEFAULT NULL, PRIMARY KEY (`id`), UNIQUE KEY `name` (`name`) --唯一索引 ) ;
- 主键索引：特殊的索引，唯一的标识一条记录，不能为空，一般用primary key来约束。
- 推荐使用自增主键，保证空间利用率，减少页分裂
CREATE TABLE `user` ( `id` int(11) unsigned NOT NULL AUTO_INCREMENT, `name` varchar(64) DEFAULT NULL, PRIMARY KEY (`id`) --主键索引 ) ;
- 全文索引：全文索引时将存储在数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获取全文中有关章，节，段，句，词等信息，也可以进行各种统计和分析。
CREATE TABLE `user` ( `id` int(11) unsigned NOT NULL AUTO_INCREMENT, `name` varchar(64) DEFAULT NULL, PRIMARY KEY (`id`), FULLTEXT KEY `name` (`name`) --创建全文索引 ) ;
按照物理实现⽅式，索引可以分为 2 种：聚簇索引和非聚簇索引。
- 聚簇索引的叶⼦节点存储的是数据，⾮聚簇索引的叶⼦节点存储的是数据位置。
- ⼀个表只有⼀个聚簇索引，但可以有多个⾮聚簇索引。
- 一般来说聚簇索引为主索引，非聚簇索引为辅助索引
数据结构
MySQL索引使用的数据结构主要有B Tree索引和hash索引。
B Tree索引
SQLite 默认使用 B 树索引
B+ Trer索引
MySQL 默认使用 B+ 树索引
hash索引
哈希索引是基于哈希表实现的，对于每一行数据，存储引擎会对索引列进行哈希计算得到哈希码，并且哈希算法要尽量保证不同的列值计算出的哈希码值是不同的，将哈希码的值作为哈希表的key值，将指向数据行的指针作为哈希表的value值。
查找一个数据的时间复杂度是O(1)，一般多用于精确查找；但是不支持范围快速查找，范围查找时只能通过扫描全表的方式，筛选出符合条件的数据。
问题与解答
Hash 索引和B+ 树索引的区别？
- 哈希索引不支持排序，因为哈希表是无序的。
- 哈希索引不支持范围查找。
- 哈希索引不支持模糊查询及多列索引的最左前缀匹配。
- 因为哈希表中会存在哈希冲突，所以哈希索引的性能是不稳定的，而B+树索引的性能是相对稳定的，每次查询都是从根节点到叶子节点。
为什么要用B树，而不是红黑树等其他树结构？
- 索引每访问一个节点，就是进行一次 I/O，树的高度越高，进行的 I/O 次数可能越多，因此为了减少 I/O 支出，我们要求树的高度尽量矮。
- 所以树结构要尽量平衡，每层都布满节点，树的高度就低了；
- 但是这样还不够，二叉树每个节点只能存一个数据，我们改为多叉树，每个节点储存多个数据，树的高度进一步降低，I/O 支出大大减少。
- 一步步优化后，最后就是 B 树。
这样并非没有代价，一个节点的数据变多，占用的内存就更多了，是一种 空间换时间 的策略。
为什么 B+ 树比 B 树更适合实现数据库索引？
- 由于B+树的数据都存储在叶子结点中，叶子结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，而在数据库中基于范围的查询是非常频繁的，所以通常B+树用于数据库索引。
- B+树的节点只存储索引key值，具体信息的地址存在于叶子节点的地址中。这就使以页为单位的索引中可以存放更多的节点。减少更多的I/O支出。
- B+树的查询效率更加稳定，任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
InnoDB 存储引擎
存储方式：数据存在磁盘中。将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB 中页的大小一般为 16 KB。
行格式
mysql 是以记录(一行数据)为单位向数据表中插入数据的，这些记录在磁盘上的存放方式称为行格式。
InnoDB 提供了 4 种行格式，分别是 Redundant、Compact、Dynamic和 Compressed 行格式。
- Redundant 是很古老的行格式了， MySQL 5.0 版本之前用的行格式，现在基本没人用了。
- Compact：由于 Redundant 不是一种紧凑的行格式，所以 MySQL 5.0 之后引入了 Compact 行记录存储方式，Compact 是一种紧凑的行格式，设计的初衷就是为了让一个数据页中可以存放更多的行记录，从 MySQL 5.1 版本之后，行格式默认设置成 Compact。
- Dynamic 和 Compressed 两个都是紧凑的行格式，它们的行格式都和 Compact 差不多，因为都是基于 Compact 改进一点东西。从 MySQL5.7 版本之后，默认使用 Dynamic 行格式。
变长字段长度列表
在Compact行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表，各变长字段数据占用的字节数按照列的顺序逆序存放。
NULL值列表
统计表中允许存储NULL值的列，然后将每个允许存储NULL值的列对应一个二进制位，（1：值为NULL，0：值不为NULL）用位图法表示是否存储NULL值。
- 如果表中没有允许存储 NULL 的列，则 NULL值列表 也不存在了
记录头信息
记录头信息是由固定的5个字节(40位)组成
行溢出
MySQL 对一条记录占用的最大存储空间是有限制的，除了 BLOB 或者 TEXT 类型的列之外，其他所有的列（不包括隐藏列和记录头信息）占用的字节长度加起来不能超过 65535 个字节。而一页最大为16KB也就是16384字节，因此可能会出现需要多张页存储一条记录的情况。
在 Compact 和 Reduntant 行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中，然后 记录的真实数据 处用20个字节存储指向这些页的地址。
在 Compact 和 Reduntant 行格式中，如果某一列中的数据非常多的话，在本记录的真实数据处只会存储该列的前 768 个字节的数据和一个指向其他页的地址，然后把剩下的数据存放到其他页中，这个过程也叫做 行溢出 ，存储超出 768 字节的那些页面也被称为 溢出页 。
Compressed 行格式和 Dynamic 不同的一点是， Compressed 行格式会采用压缩算法对页面进行压缩，以节省空间。
页结构
页类型
页通用结构
任何类型的页都会包含这两个部分：
- File Header：记录页的一些通用信息
（ IL_PAGE_PREV 和 FIL_PAGE_NEXT 来存储上一个页和下一个页的页号，是 B+ 树每层节点建立双向链表用的，一般类型的页是不使用这两个字段的。）
- File Trailer：共八字节，校验页是否完整，保证从内存到磁盘刷新时内容的一致性。
- 前四个字节代表页的校验和
- 后四个字节代表文件最后修改时对于的 LSN 值
数据页
结构：
Page Directory：InnoDB会为把页中的记录划分为若干个组，每个组的最后一个记录的地址偏移量作为一个 slot，存放在Page Directory中，所以在一个页中根据主键查找记录是非常快的，分为两步：
- 通过二分法确定该记录所在的 slot。
- 通过记录的next_record属性遍历该 slot 所在的组中的各个记录。
为保证从内存中同步到磁盘的页的完整性，在 File Header 和 File Trailer 都会存储页中数据的校验和和页面最后修改时对应的 LSN 值，如果 File Header 和 File Trailer 的校验和和 LSN 值校验不成功的话，就说明同步过程出现了问题。
区（extent）
为了管理页，提出了区的概念。连续的64个页就是一个区，也就是说一个区默认占用1MB空间大小。256个区为一组。
在表中数据量大 的时候，为某个索引分配空间的时候就不再按照页为单位分配了，而是按照 区 为单位分配
为什么要提出区？
我们每向表中插入一条记录，本质上就是向该表的聚簇索引以及所有二级索引代表的 B+ 树的节点中插入数 据。而 B+ 树的每一层中的页都会形成一个双向链表，如果是以 页 为单位来分配存储空间的话，双向链表相邻的两个页之间的物理位置可能离得非常远，导致随机 I/O。随机 I/O 很慢，所以我们应该尽量让链表中相邻的页的物理位置也相邻，才能使用顺序 I/O。
所以提出了 区。
段
段不对应表空间中某一个连续的物理区域，而是一个逻辑上的概念，由若干个零散的页面（碎片区）和一系列完整的区组成。。段一般分为：
- 索引段：存放 B + 树的非叶子节点的区的集合；
- 数据段：存放 B + 树的叶子节点的区的集合；
- 回滚段：存放的是回滚数据的区的集合
表空间
在 MySQL5.6.6 之后，InnoDB 并不会默认地把各个表的数据存储到系统表空间中，而是为每一个表建立一个独立表空间。创建一个表后，会在该表所属数据库对应的子目录下创建一个表示该独立表空间的文件，文件名为 表名.ibd。
可以指定使用系统表空间还是独立表空间来存储数据，这个功能由启动参数 innodb_file_per_table 控制，在 my.cnf 配置文件中。
索引方式
在InnoDB存储引擎中，默认的索引为B+树索引，利用主键创建的索引为主索引，是聚簇索引；在主索引之上创建的索引为辅助索引，是非聚簇索引。
MyISAM 存储引擎
MyISAM提供了大量的特性，包括全文索引、压缩、空间函数(GIS)等，但MyISAM 不支持事务、行级锁、外键 ，有一个毫无疑问的缺陷就是 崩溃后无法安全恢复 。
是MySQL 5.5之前默认的存储引擎
索引方式
在MyISAM存储引擎中，默认的索引也是B+树索引，但主索引和辅助索引都是非聚簇索引，也就是说索引结构的叶子节点存储的都是一个指向数据行的地址。并且使用辅助索引检索无需访问主键的索引。
InnoDB 和 MyISAM 的区别
- 锁的细粒度不同：InnoDB 比 MyISAM 更好的支持并发，因为 InnoDB 的支持行锁，而 MyISAM 支持表锁，行锁对每一条记录上锁，所以开销更大，但是可以解决脏读和不可重复读的问题，相对来说也更容易发生死锁。
- 可恢复性：InnoDB 有事务日志，数据库崩溃后可以通过日志进行恢复，MyISAM 没有日志支持。
- 查询性能：MyISAM 要好于 InnoDB，因为 InnoDB 在查询过程中是在维护数据缓存。并且先要定位到所在数据块，然后从数据块定位到数据内存地址来查找数据。
- 表结构文件：MyISAM 的表结构文件包括 .frm(表结构定义)，.MYI(索引)、.MYD（数据）；而InnDB的表数据文件为 .ibd(数据和索引集中存储)和.frm(表结构定义)。
- 记录存储顺序：MyISAM 按照记录插入顺序，InnoDB 按照主键大小顺序有序插入。
- 外键和事务：MyISAM 均不支持，InnoDB 支持。对于 InnoDB 每一条SQL语言都默认封装成事务，自动提交，这样会影响速度，所以最好把多条 SQL 语言放在 begin 和 commit 之间，组成一个事务。对一个包含外键的 InnoDB 表转为 MYISAM 会失败。
- 操作速度：对于 SELECT，MyISAM 更优，而对于 INSERT、UPDATE、DELETE，InnoDB 更优。select count * 使用MyISAM更块，因为内部维护了一个计数器，可以直接调度。
- 存储空间：MyISAM 可被压缩，存储空间较小，InnoDB 的表需要更多的内存和存储，会在主内存中建立专用的缓冲池用于高速缓存数据和索引。