共计 4660 个字符，预计需要花费 12 分钟才能阅读完成。
聚簇 (汇集) 索引
聚簇索引 (InnoDB) 是对磁盘上的数据从新组织以按指定的一个或多个列的值排序的算法，聚簇索引的叶子节点就是其 数据节点 ，其特点是数据的存储程序和索引程序统一。
个别状况下默认以主键为聚簇索引，且一张表只容许存在一个聚簇索引，因为，数据一旦存储，其程序只能有一种 。
如果未设置主键，会抉择一个符合条件的 Unique-key 做主键；如果找不到符合条件的 Unique-key，InnoDB 会生成一个外部的 rowid 做主键;
非聚簇 (汇集) 索引
非聚簇索引 (MyISAM) 的叶子节点依然是索引文件，只是这个索引文件中蕴含指向对应数据块的指针。
二者区别（征引自数据库原理一书）：
聚簇索引的叶子节点就是其数据节点，而非聚簇索引的叶子节点依然是索引节点，该索引节点指向对应数据块的指针。
聚簇索引的优缺点：
长处: 依据主键查问条目比拟少时，不必回表 (数据就在主键节点下)；
毛病: 如果碰到不规则数据插入时，造成频繁的页决裂；
对于聚簇索引的长处：
InnoDB 的二级索引的叶子节点寄存的是索引 key 值和主键值；因而执行相似 select * 查问全量字段时，会先通过二级索引定位到主键值，再依据查到的主键值执行一遍主键索引找到相应的数据块，这个过程叫做 回表 ;
可见，回表的实质是两次二叉树查问，所以个别不倡议应用 select *；
而如果查问的字段就是索引 key 自身，则称之为 笼罩索引 ；
比方学生表里除了 学生 ID，还有 学生姓名、班级 ID、业余 ID等，假如以 学生 ID、班级 ID 做了联结索引，那么当咱们 select 学生 ID、班级 ID from 班级表 时，通过二级索引，就会找到咱们须要的值，无需再应用主键回表，会大大节省时间。
MyISAM 的主键和二级索引的叶子节点，保留的都是其数据的物理地址；
因而，MyISAM，无论是用主键还是二级索引，都要回表查问；
也因这个个性，MyISAM 能够不设主键！于 MyISAM 而言，主键索引和二级索引，其实没啥区别，只不过主键因其定义的特殊性，需保障惟一、非空；
对于聚簇索引的毛病：
InnoDB 环境下，页决裂会产生在插入或更新，为满足索引逻辑，可能会产生频繁的页决裂，从而导致更新效率变低；
MyISAM 不存在页决裂的问题：只需在更新数据之后挪动索引节点即可；
什么是页决裂？
咱们要晓得，InnoDB 不是按行来操作数据的，它可操作的最小单位是 页，页加载进内存后才会通过扫描页来获取行记录。
比方查问 id=111，是获取111 所在的数据页，加载进内存后取出 111 这一行。
页的默认大小为 16KB，64 个间断的数据页称为一个 extent（区），64 个页组成一个区，所以区的大小为 1MB(16*64=1024)，间断的 256 个数据区称为一组数据区；
两个数据页之间会有指针指向上一个和下一个数据页，造成一个双向链表，数据页中的每个数据行之间会有单向指针连贯，组成一个单向链表；
当一个数据页中的数据行太多放不下的下，就会生成一个新的数据页来存储，同时应用双向链表来相连；
应用索引时，一个最根底的条件是，前面数据页中的数据行的主键值要大于前一个数据页中数据行的主键值；
至于起因，其实索引简略来说，就是一遍一遍过筛子，通过二分法的逻辑一直缩小要筛选的数据，而实在数据是按主键顺序存储的，所以主键值就是筛选规范，以便尽快定位咱们须要的数据；
咱们假如如下的前两行数据已满足凑成一页的条件 ：
如果咱们设置了主键 ID 自定义，非自增，在曾经插入了 1、5、6、7(已分为两页) 等 ID 的状况下，再插入 ID2，就会触发页决裂；
因为咱们须要保障，后一个数据页中的所有主键值要比前一个数据页中的主键值大 ；
这时我咱们须要把 2 插入到 1 的前面，5、6、7等 ID 顺次后移；
留神，这里不是单纯的挪动 ID，而是要带着数据一起搬家！另外，每一行数据所占用的空间是不固定的，有可能挪动之后，一页空间存不下 5、6、7 三条数据，须要同时生成第三页寄存 7ID;
如果第三页曾经存在了咋办，那就得生成第 N 页，同时批改第二、三页和第 N 页的指针，调整到符合要求；
所以如果插入的主键是乱序，为满足索引条件，可能会产生频繁的页决裂，从而导致更新效率变低；
当然了，真正的页决裂要比下面所说的简单很多，但实质是通过这种逻辑来实现页决裂的。
文档参考：https://www.percona.com/blog/innodb-page-merging-and-page-splitting
文档翻译参考：https://zhuanlan.zhihu.com/p/98818611页决裂的大抵流程
假如当初有 9、10、11 等 3 页数据，在页 #10 中插入了乱序的主键 ID，或者更新了一条长文本数据导致当没有足够空间存储：
因为页 #10 没有足够空间去包容新（或更新）的记录，依据“下一页”逻辑，记录应该由页#11 负责。然而：页#11 也同样满了，为了保障主键的程序，也不可能乱序插入。这时候该怎么办呢？
B+ 树的每一层都是双向链表，页 #10 有指向页#9 和页#11 的指针，InnoDB 的做法是（简化版）：
- 创立新页
- 判断当前页（页 #10）能够从哪里进行决裂（记录行层面）
- 挪动记录行
- 从新定义页之间的关系
新的页 #12 被创立(假如只存在#13 页，#12 页被合并后删除了)，页#11 放弃原样，只有页之间的关系产生了扭转：
- Page #10 will have Prev=9 and Next=12
- Page #12 Prev=10 and Next=11
- Page #11 Prev=12 and Next=13
B 树在程度方向的一致性依然满足，然而，在物理上，页面的地位却是无序的，而且大概率会落到不同的区。
总结：页面拆分产生在插入或更新时，并会导致页的错位（dislocation，落入不同的区）。
InnoDB 用 INFORMATION_SCHEMA.INNODB_METRICS 表来跟踪页的决裂数。能够查看其中的 index_page_splits 和 index_page_reorg_attempts/successful 统计。
一旦产生了决裂的页，MySQL 本身 (无人为干涉) 惟一将原先程序复原的方法就是新决裂进去的页因为低于合并阈值（merge threshold）被删掉。这时候 InnoDB 会应用页合并将数据从新合并回来。
人为干涉的形式就是用 OPTIMIZE 从新整理表。这可能是个很重量级和耗时的过程，但通常是惟一将大量扩散在不同区的页理顺的办法。
另一方面，在页的合并和决裂期间，InnoDB 会获取索引树的 x-latch。它可能会导致索引的锁争用（index latch contention）。
如果没有合并和拆分(有写操作)，称为“乐观”更新，只需应用读锁（S）。带有合并和决裂的操作则称为“乐观”更新，需应用写锁（X）。
衍生知识点：页合并
依据 B-Tree 的个性，InnoDB 能够自顶向下遍历，也能够在各叶子节点之间程度遍历，因为每个叶子节点都有一个指向下一条（程序）记录页的指针；
例如，页 -5 有指向 页 -6 的指针，页 -6 有指向前一页（5）的指针和后一页（7）的指针；
如果是基于自增主键进行插入，这种机制能够做到疾速程序扫描（如范畴扫描），但如果你不仅插入还进行删除呢？
首先，删除一行记录时，实际上记录并没有被物理删除，只是被临时标记（flaged）为删除，且它的空间变得容许被其余记录应用；
其次，当页中删除的记录达到 MERGE_THRESHOLD（默认页体积的 50%） 时，InnoDB 会开始寻找最靠近的页（前或后）看看是否能够将两个页合并以优化空间应用；
如果第 N 页应用了不到一半的空间，第 N-1 页又达到了足够的删除数量，且同样处于 50% 应用以下，这时 InnoDB 会尝试将这两页合并；
合并后，第 N-1 页保留它之前的数据，并且包容来自第 N 页的数据，同时，第 N 页变成一个空页，能够接收新数据。
基于这个逻辑，咱们能够得出，如果 UPDATE 操作让页中数据体积达到下面的的阈值点，同样会触发页合并 ；
所以，页合并产生在删除或更新操作中，关联到当前页的相邻页；
如果页合并胜利，在 INFOMATION_SCHEMA.INNODB_METRICS 中的 index_page_merge_successful 将会减少。
问题延长 -1: 3 层 B+ 树 的 InnoDB 可存储多少行数据？
InnoDB 构建 B+ 树 是以页为最小单位，参考下面的解释，所以咱们可得出如下论断：
- 1、如果树的高度 3，那么前 2 层存储的为 索引键值和页指针，第三层叶子节点才会存储数据；
- 2、根节点页如果为为默认值
16kb，则为可存储的 索引键值和页指针 的下限；
可执行show variables like 'innodb_page_size'查看以后库设置的 页大小； - 3、指针占 6 字节 (官网材料)，bigint 类型的主键占 8 字节，加和共 14 字节，则根节点可存储的索引条数为：
16kb * 1024 / 14 字节 = 1170；
咱们假如一行数据占用1kb的空间，也就是一页可寄存 16 条记录，这个设定是为了不便计算，理论的行大小可能远小于 1kb；
如果以后只有 2 层B+ 树，则可存储的行数为：1170*16=18720;
当初拓展为 3 层B+ 树，根节点不再间接指向数据页，而是指向第二层索引页，即根节点的每一条索引指向一个 16kb 的索引页，则可存储的索引条数演变为1170*1170，即 1170 的 2 次方；
由此可得出，3 层B+ 树可存储：1170*1170*16=21902400，约两千万条记录；
持续延长，按以上设定，N 层B+ 树可存储的记录数为:1170 的 (N-1) 次方 * 16;
附，根节点 变动逻辑：
- 当为某个表创立一个 B + 树索引时，都会为这个索引创立一个 根节点 页；
- 最开始表中没数据时，每个 B + 树索引对应的 根节点 中既没数据记录，也没索引记录；
- 开始插入数据后，会先存储到根节点，当根节点空间被用完后，会将 根节点中所有记录复制到一个新的调配页，本来的 根节点 会变为存储记录页的索引目录页，整个过程 根节点 不会挪动；
- 根节点 并不是向上创立目录页，而是将根节点本身变为目录页，本来根节点的数据会被复制一份到根节点下方，而后再在根节点上创立新的子节点存储新的记录；新插入的记录依据键值（聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被调配到对应页中，而根节点便降级为存储目录项的记录页。
这就是 B+ 树 的演变过程。这个过程特地留神的是：一个 B + 树索引的根节点自诞生之日起，便不会再挪动。这样只有咱们对某个表建设一个索引，那么它的根节点的页号便会被记录到某个中央，而后但凡 InnoDB 存储引擎须要用到这个索引的时候，都会从那个固定的中央取出根节点的页号，从而来拜访这个索引。
面试 -Summary：
- InnoDB 的主索引文件中间接寄存该行数据，称为聚簇索引，次索引 (二级索引) 指向对主键的援用；
- MyISAM 的主索引和次索引，都指向物理行地址(磁盘地位)；
- InnoDB(聚簇索引)的主键值最好是有序的，不仅能充沛应用到索引，还尽可能防止了页决裂；否则就必须进行页决裂来保障索引的逻辑正确性；
- InnoDB 的主键，尽量应用间断增长的值，而不是随机值(比方随机字符串或 UUID), 否则可能产生大量的页决裂；
- InnoDB 的 B + 树索引注意事项：根页面的地位万年不动，一个页面起码存储 2 条记录。
- 聚簇索引的叶子节点存储的是行数据；而非聚簇索引叶子节点存储的是聚簇索引（通常是主键 -ID）。
- 聚簇索引查问效率更高，而非聚簇索引须要进行回表查问，因而性能不如聚簇索引。
- 聚簇索引一个表中只能有一个，而非聚簇索引则没有数量上的限度。
