> 我一个后端不会 MySQL 那我还不如直接离职 (入职的时候听到同事说的) 不太确定这一篇文章是作为目录还是作为一篇笔记，总之先记录后续在重构吧 --- # 1. 基础知识？ 这一块后面统一按照总结一下？ # 2. 索引   关于[索引](https://baike.baidu.com/item/%E7%B4%A2%E5%BC%95/5716853?fr=aladdin)的定义，通俗点来说就是对<font color="#FF0000">数据库表中一列或多列的值进行排序的一种结构</font> 。而它的作用就是极大的加快 `MySQL` 的查询效率。 ## 2.1 索引类型   数据库的索引类型分为逻辑分类和物理分类 - 逻辑分类： - **主键索引(PRIMAY KEY)：** 当关系表中定义主键时会自动创建主键索引。每张表中的主键索引只能有一个，要求主键中的每个值都唯一，即不可重复，也不能有空值。 - 最常见的索引类型，确保数据的唯一性，确定特定的数据记录在数据库中的位置 - **唯一索引(UNIQUE)：** 数据列不能有重复，可以有空值。一张表可以有多个唯一索引，但是每个唯一索引只能有一列。 - 与主键索引相同 - **普通索引(INDEX)：** 一张表可以有多个普通索引，可以重复可以为空值 - **全文索引(FULLTEXT)：** 可以加快模糊查询，不常用 - 只能用于 <font color="#FF0000">`MyISAM`</font> 类型的数据表，只能用于 `CHAR` ,`VARCHAR`,`TEXT` 数据列类型 ## 2.2 为什么需要索引？   对于数据库而言，查询功能是在使用过程中最高频的操作。对于查询而言能想到的算法有最基本的 `linear search`，稍微进阶的 `binary search`，以及 `binary tree search` 等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如 `binary search` 就只能用在有序数据上，而 `binary tree search` 就只能用在二叉排序树上。所以为了加快查询的效率就必须使用某种查询算法来优化查询的方法，进而需要使用某种数据结构来满足算法的使用条件。但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。 ## 2.3 索引的结构    上图展示了一种可能的索引方式。左边是数据表，其中最左边一列是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快 `Col2` 的查询速度维护了一个像右侧这样的二叉排序树，这样就可以通过二叉排序树来搜索，时间复杂度由 $O(n)$ --> $O(logn)$。但是数据库并没有使用二叉查找树或其进化品种红黑树实现的，<font color="#FF0000">针对于特殊情况而言上述两种数据结构会退化为一条链或者树非常深</font>，所以它们的效率相对于 `B tree`/`B+ tree` 以及 `HASH` 来说特别的低。 ### 2.3.2 HASH 索引    上图展示了基于 `HASH` 表的索引格式，很好理解同时如果想要更深入的了解 `HASH` 请[移步](https://neo00.top/archives/%E6%95%A3%E5%88%97%E8%A1%A8hashtable)。这里主要分析下优劣： - **优点：** - 如果 `HASH` 算法设计的好，冲突发生的少那么这个查询的速度是非常快的 - **缺点：** - 容易发生冲突 - 利用 `HASH` 存储需要把所有数据文件加载到内存，非常耗费内存空间 - 对于范围查询 `HASH` 效率非常低 - Memory 存储引擎使用 `HASH` 索引作为默认索引 ### 2.3.3 二叉排序树 / 平衡树 / 红黑树    上图展示了基于二叉树排序树(AVL情况基本类似不做额外补充)，以及红黑树的索引形式。想了解更多关于这三种数据机构的请[移步](https://neo00.top/archives/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91)。   根据上图很容易看到二者的弊端，<font color="#FF0000">当数据过多时都会导致树的深度过大，**导致I/O次数增多**，影响查询效率</font>。 ### 2.3.3 B tree / B+ tree #### 2.3.3.1 局部性原理与磁盘预读    在分析这两个数据结构的性能前先要介绍一个基础知识 **局部性原理与磁盘预读**。由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上刺针移动机械运动的耗费，磁盘的存取速度往往时主存的击败倍，而MySQL优化的主要瓶颈就在 `I/O` 操作上，所以要尽可能减少 `I/O` 次数。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会<font color="#FF0000">预读</font>，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论就是计算机科学中的局部性原理： - 当一个数据被用到时，其附近的数据也通常马上会被使用。 - 程序运行期间所需的数据通常比较集中。 - 磁盘顺序 `I/O` 的效率远大于随机 `I/O`，对于局部性程序来说，预读可以提高 `I/O` 效率。   而操作系统的存储又是分页的，所以预读的长度一般为页(page)的整数倍。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(默认4KB)，主存和磁盘以页为单位进行数据交换。当程序要读取的数据不在主存中，会触发一个缺页异常，此时系统会像磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页加载到内存中，然后异常返回，程序继续执行。 ---   首先分析 `B tree` 为什么能优化 `I/O` 效率。根据 `B tree` 的定义，有一个度(degree)的概念。这代表着 `B tree` 不会像二叉树或者红黑树那样每个节点只保存一个值，而是会保存很多个值，下图一个 `MaxDegree == 4` 的 `B tree`。    数据库系统巧妙的利用了磁盘预读原理，将一个节点的大小设为等于一页，这样每个节点只需要一次 `I/O` 就可以完全载入到内存中。针对于上述数据结构图画出了如下的数据库的样例图：    根据上图可以看到，每个节点占用一个磁盘块，一个节点上有两个升序排列的关键字以及三个指向叶子节点的指针，指针存储的是叶子节点所在磁盘块的地址。两个关键字划分成三个范围域对应三个指针指向子树 的数据范围域。假定需要查找 `28` 那么查找过程如下： 0. 每个磁盘块会有很多关键字，可以通过二分快速确定区间 1. 跟节点常驻内存空间，根节点(磁盘块1)读入内存。【第一次 I/O】 2. 比较关键字 28，在区间 (16, 43)，找到`磁盘块1`的指针 `P2`。 3. 根据 `P2` 指针找到 `磁盘块3`，读入内存 【第二次 I/O】。 4. 比较关键字 28，在区间 (25, 31)，找到`磁盘块3`的指针 `P2`。 5. 根据 `P2` 指针找到 `磁盘块8`，读入内存 【第三次 I/O】。 6. 比较关键字 28，找到对应数据返回。   通过上述一次查询可以发现，一共进行了三次 `I/O` 操作，针对 `InnoDB` 引擎而言，每次会读取 `4 X 4KB` 的数据，所以三次 `I/O` 一共会读取 `48K` 的数据到内存中。而存储的数据量，假定每个磁盘块每个节点的数据大小都是 `1KB`，那么经过三次 `I/O` 一共会存储 $16 * 16 * 16$ 也就是 $4096$ 个数据块相比于前面几种数据结构，无论是在 `I/O` 次数上还是存储的数据量上都有质的提升。 --- 分析完了 `B tree`，来分析下 `B+ tree`。下图是一个 `MaxDegree == 4` 的 `B+ tree`。  从图上看与 `B tree` 有几个很明显的区别： 1. B+ tree 会冗余一份父节点的数据到子节点中 2. B+ tree 在叶子节点增加了双向指针(图中只画出的单向) 而根据 `B+ tree` 的数据结构图画出了如下的数据库的样例图：    从上面分析可以看到，`MaxDegree` 越大索引的性能越好，而出度的上限取决于节点内 `key` 和 `data` 的大小：MaxDegree = floor( pagesize / ( keysize + datasize+pointsize ))。由于 `B+ tree` 只在叶节点才有 `data` 域，内节点去掉了 `data` 域，因此可以拥有更大的出度，拥有更好的性能，<font color="#FF0000">读取同样大小的数据 `B+ tree` 比 `B tree` 增加的数据是呈指数增长的。同时，`B+ tree` 在叶子节点增加了双向指针，这样更加有利于在 `SQL` 中执行范围查找，极大地提高了区间访问的性能。</font>    `B+ tree` 有2个头指针，一个是树的根节点，一个是最小关键码的叶节点，所以 `B+ tree`提供了两种查询方法： 1. 按叶节点自己拉起的链表顺序搜索 2. 从根节点开始搜索，和 `B tree` 类似，不过如果非叶节点的关键码等于给定值，搜索并不停止，而是继续沿右指针，一直查到叶节点上的关键码。所以无论搜索是否成功，都将走完树的所有层。 #### 2.3.3.2 总结   经过上述分析，总结 `B tree` 与 `B+ tree` 的区别 1. **关键字的数量不同；** `B+ tree` 中分支结点有 `m` 个关键字，其叶子结点也有 `m` 个，其关键字只是起到了一个索引的作用，但是 `B tree` 虽然也有 `m` 个子结点，但是其只拥有m-1个关键字。 2. **存储的位置不同；** `B+ tree` 中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是 `B tree` 的数据存储在每一个结点中，并不仅仅存储在叶子结点上。 3. **分支结点的构造不同；** `B+ tree` 的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。 4. **查询不同；** `B tree` 在找到具体的数值以后，则结束，而 `B+ tree` 则需要通过索引找到叶子结点中的数据才结束，也就是说 `B+ tree` 的搜索过程中走了一条从根结点到叶子结点的路径。 为什么选择 `B+ tree` 作为索引的实现方式？   `B+ tree` 的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是 `B tree`因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以 `B+ tree` 更加适合在区间查询的情况，所以通常 `B+ tree` 用于数据库索引，而 `B tree` 则常用于文件索引。 ## 2.4 MyISAM 和 InnoDB 不同的索引实现   在 `MySQL` 中，索引属于**存储引擎级别的概念**，不同存储引擎对索引的实现方式是不同的，本文主要讨论 `MyISAM` 和 `InnoDB` 两个存储引擎的索引实现方式。 ### 2.4.1 MyISAM 索引实现 #### 2.4.1.1 主键索引    `MyISAM` 引擎使用 `B+ tree` 作为索引结构，叶节点的 `data` 域存放的是数据记录的地址。下图是 `MyISAM` 索引的原理图：  #### 2.4.1.2 辅助索引   在 `MyISAM` 中，主索引和辅助索引在结构上没有任何区别，**只是主索引要求 `key`是唯一的，而辅助索引的 `key` 可以重复。**    同样也是一颗 `B+ tree`，`data` 域保存数据记录的地址。因此，`MyISAM` 中索引检索的算法为首先按照`B+ tree` 搜索算法搜索索引，如果指定的 `Key` 存在，则取出其 `data` 域的值，然后以 `data` 域的值为地址，读取相应数据记录.所以<font color="#FF0000"> `MyISAM` 实现的索引称为非聚簇索引。</font> ### 2.4.2 InnoDB 索引实现 #### 2.4.2.1 主键索引    `MyISAM` 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在 `InnoDB` 中，表数据文件本身就是按 `B+ tree` 组织的一个索引结构，这棵树的叶节点 `data` 域 保存了完整的数据记录。 这个索引的 `key` 是数据表的主键，因此 `InnoDB` 表数据文件本身就是主索引。    上图所示，`InnoDB` 主键索引的叶节点包含了完整的数据记录（数据文件），<font color="#FF0000"> `InnoDB`实现的索引叫做**聚簇索引**。</font>，同时 `InnoDB` 实现的索引有以下几个特点： - 因为 `InnoDB` 的数据文件本身要按主键聚集，所以 `InnoDB` 要求表必须有主键（`MyISAM`可以没有）， - 如果没有显式指定，则 `MySQL` 系统会自动选择一个可以唯一标识数据记录的列作为主键， - 如果不存在这种列，则 `MySQL` 自动为 `InnoDB` 表生成一个隐含字段(row_id)作为主键，这个字段长度为6个字节，类型为长整形，这个字段用户不感知。 #### 2.4.2.2 辅助索引 `InnoDB` 的所有辅助索引都引用主键作为 `data` 域。    文字符的ASCII码作为比较准则。<font color="#FFA500"> **聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索 两遍索引 ：首先 检索辅助索引获得主键，然后 用主键到主索引中检索获得记录。**</font> ### 2.4.3 InnoDB 索引和 MyISAM 索引的区别 1. **主索引的区别：**`InnoDB` 的数据文件本身就是索引文件。而 `MyISAM` 的索引和数据是分开的，非聚簇索引与聚簇索引 2. **辅助索引的区别：** `InnoDB` 的辅助索引 `data` 域存储相应记录主键的值而不是地址, `MyISAM` 的辅助索引和主索引没有多大区别 # 3. 总结 **普通二叉搜索树当索引的劣势：** 1. 每个节点占用的空间太少，不能很好的利用磁盘的预读性。 2. 对于某些特殊数据会退化为链表 3. 存储的数据少，导致频繁 `I/O` **B tree 当索引机制相比于二叉树的优势和劣势：** 1. 每个节点有关键字、数据区、子节点指针。 2. 每个节点存储的数据多，可以充分的利用预读性（InnoDB一个磁盘块默认是16KB） 3. 退化的程度情况减少 4. 单次读取的数据多同时节点存储的数据多，减少 `I/O` 次数 **B+ tree 相比于 B tree 的优势：** 1. ）因为每个节点不存数据区（内存地址）了，所有每个节点的度可以更多，这样树的高度可以变矮很多，更利于查找 2. 数据区都在叶子节点存着，一条链表，在排序时更有优势 3. `B+ tree` 的节点变换时，是分裂形式而不是 `B tree` 的左旋转(右旋转)形式，效率高 4. 但是 `B+ tree` 有个缺点，就是不论查什么数据都必须要遍历到叶子节点才可以拿到真实的数据地址 **MyISAM 和 InnoDB 的索引机制的不同：** 1. `MyISAM` 的索引和数据区是分成两个文件来分别存储的，`InnoDB` 的数据区是和主键索引放在一起的 2. `MyISAM` 的每个索引都是单独的一棵树，每个索引都存储有真实的数据区地址，而 `InnoDB` 只有主键索引树才存储有真实地址，而辅助索引树的叶子节点存储的是主键的关键字 3. `MyISAM` 每个索引树都可以独当一面，而 `InnoDB` 的辅助索引树就算找到了对应的关键字，也还是要到叶子节点拿到主键的关键字，然后再去主键索引树遍历 4. `MyISAM` 没有默认的主键索引，而 `InnoDB` 有默认的主键索引（聚集索引）（不明确指定的情况下），`InnoDB` 除了主键索引是聚集索引，其他都是非聚集索引 # 4. 附录 - [wezheng -- MySQL数据库中的索引（一）——索引实现原理](https://www.cnblogs.com/wezheng/p/8394026.html) - [B+树在 MyISAM 和 InnoDB 的不同实现方式（图） ](https://blog.csdn.net/xiaojin21cen/article/details/105776695)