MySQL的InnoDB索引原理详解（讲的很好）
本篇介绍下Mysql的InnoDB索引相关知识，从各种树到索引原理到存储的细节。
InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM，)。本着⾼效学习的⽬的，本篇以介绍InnoDB为主，少量涉及MyISAM作为对⽐。
这篇⽂章是我在学习过程中总结完成的，内容主要来⾃书本和博客(参考⽂献会给出)，过程中加⼊了⼀些⾃⼰的理解，描述不准确的地⽅烦请指出。
1 各种树形结构
本来不打算从⼆叉搜索树开始，因为⽹上已经有太多相关⽂章，但是考虑到清晰的图⽰对理解问题有很⼤帮助，也为了保证⽂章完整性，最后还是加上了这部分。
先看看⼏种树形结构：
1 搜索⼆叉树：每个节点有两个⼦节点，数据量的增⼤必然导致⾼度的快速增加，显然这个不适合作为⼤量数据存储的基础结构。
2 B树：⼀棵m阶B树是⼀棵平衡的m路搜索树。最重要的性质是每个⾮根节点所包含的关键字个数 j 满⾜：┌m/2┐ – 1 <= j <= m – 1；⼀个节点的⼦节点数量会⽐关键字个数多1，这样关键字就变成了⼦节点的分割标志。⼀般会在图⽰中把关键字画到⼦节点中间，⾮常形象，也容易和后⾯的B+树区分。由于数据同时存在于叶⼦节点和⾮叶⼦结点中，⽆法简单完成按顺序遍历B树中的关键字，必须⽤中序遍历的⽅法。
3 B+树：⼀棵m阶B树是⼀棵平衡的m路搜索树。最重要的性质是每个⾮根节点所包含的关键字个数 j 满⾜：┌m/2┐ – 1 <= j <= m；⼦树的个数最多可以与关键字⼀样多。⾮叶节点存储的是⼦树⾥最⼩的关键字。同时数据节点只存在于叶⼦节点中，且叶⼦节点间增加了横向的指针，这样顺序遍历所有数据将变得⾮常容易。
4 B*树：⼀棵m阶B树是⼀棵平衡的m路搜索树。最重要的两个性质是1每个⾮根节点所包含的关键字个数 j 满⾜：┌m2/3┐ – 1 <= j <= m；2⾮叶节点间添加了横向指针。
mysql下载32位
B/B+/B*三种树有相似的操作，⽐如检索/插⼊/删除节点。这⾥只重点关注插⼊节点的情况，且只分析他们在当前节点已满情况下的插⼊操作，因为这个动作稍微复杂且能充分体现⼏种树的差异。与之对⽐的是检索节点⽐较容易实现，⽽删除节点只要完成与插⼊相反的过程即可（在实际应⽤中删除并不是插⼊的完全逆操作，往往只删除数据⽽保留下空间为后续使⽤）。
先看B树的分裂，下图的红⾊值即为每次新插⼊的节点。每当⼀个节点满后，就需要发⽣分裂（分裂是⼀个递归过程，参考下⾯7的插⼊导致了两层分裂），由于B树的⾮叶⼦节点同样保存了键值，所以已满节点分裂后的值将分布在三个地⽅：1原节点，2原节点的⽗节点，3原节点的新建兄弟节点（参考5，
7的插⼊过程）。分裂有可能导致树的⾼度增加（参考3，7的插⼊过程），也可能不影响树的⾼度（参考5，6的插⼊过程）。
B+树的分裂：当⼀个结点满时，分配⼀个新的结点，并将原结点中1/2的数据复制到新结点，最后在⽗结点中增加新结点的指针；B+树的分裂只影响原结点和⽗结点，⽽不会影响兄弟结点，所以它不需要指向兄弟节点的指针。
B*树的分裂：当⼀个结点满时，如果它的下⼀个兄弟结点未满，那么将⼀部分数据移到兄弟结点中，
再在原结点插⼊关键字，最后修改⽗结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）。如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在⽗结点增加新结点的指针。可以看到B*树的分裂⾮常巧妙，因为B*树要保证分裂后的节点还要2/3满，如果采⽤B+树的⽅法，只是简单的将已满的节点⼀分为⼆，会导致每个节点只有1/2满，这不满⾜B*树的要求了。所以B*树采取的策略是在本节点满后，继续插⼊兄弟节点（这也是为什么B*树需要在⾮叶⼦节点加⼀个兄弟间的链表），直到把兄弟节点也塞满，然后拉上兄弟节点⼀起凑份⼦，⾃⼰和兄弟节点各出资1/3成⽴新节点，这样的结果是3个节点刚好是2/3满，达到B*树的要求，皆⼤欢喜。
B+树适合作为数据库的基础结构，完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问（随机访问即给出任意⼀个地址，要求返回这个地址存储的数据）但是容量较⼩。⽽硬盘的随机访问要经过机械动作（1磁头移动 2盘⽚转动），访问效率⽐内存低⼏个数量级，但是硬盘容
量较⼤。典型的数据库容量⼤⼤超过可⽤内存⼤⼩，这就决定了在B+树中检索⼀条数据很可能要借助⼏次磁盘IO 操作来完成。如下图所⽰：通常向下读取⼀个节点的动作可能会是⼀次磁盘IO操作，不过⾮叶节点通常会在初始阶段载⼊内存以加快访问速度。同时为提⾼在节点间横向遍历速度，真实数据库中可能会将图中蓝⾊的CPU计算/内存读取优化成⼆叉搜索树（InnoDB中的page directory机制）。
真实数据库中的B+树应该是⾮常扁平的，可以通过向表中顺序插⼊⾜够数据的⽅式来验证InnoDB中的B+树到底有多扁平。我们通过如下图的CREATE语句建⽴⼀个只有简单字段的测试表，然后不断添加数据来填充这个表。通过下图的统计数据（来源见参考⽂献1）可以分析出⼏个直观的结论，这⼏个结论宏观的展现了数据库⾥B+树的尺度。
1 每个叶⼦节点存储了468⾏数据，每个⾮叶⼦节点存储了⼤约1200个键值，这是⼀棵平衡的1200路搜索树！
2 对于⼀个22.1G容量的表，也只需要⾼度为3的B+树就能存储了，这个容量⼤概能满⾜很多应⽤的需要了。如果把⾼度增⼤到4，则B+树的存储容量⽴刻增⼤到25.9T之巨！
3 对于⼀个22.1G容量的表，B+树的⾼度是3，如果要把⾮叶节点全部加载到内存也只需要少于18.8M的内存（如何得出的这个结论？因为对于⾼度为2的树，1203个叶⼦节点也只需要18.8M空间，⽽22.1G从良表的⾼度是3，⾮叶节点1204个。同时我们假设叶⼦节点的尺⼨是⼤于⾮叶节点的，因为叶⼦节点存储了⾏数据⽽⾮叶节点只有键和少量数据。），只使⽤如此少的内存就可以保证只需要⼀次磁盘IO操作就检索出所需的数据，效率是⾮常之⾼的。
2 Mysql的存储引擎和索引
可以说数据库必须有索引，没有索引则检索过程变成了顺序查，O(n)的时间复杂度⼏乎是不能忍受的。我们⾮常容易想象出⼀个只有单关键字组成的表如何使⽤B+树进⾏索引，只要将关键字存储到树
的节点即可。当数据库⼀条记录⾥包含多个字段时，⼀棵B+树就只能存储主键，如果检索的是⾮主键字段，则主键索引失去作⽤，⼜变成顺序查了。这时应该在第⼆个要检索的列上建⽴第⼆套索引。这个索引由独⽴的B+树来组织。有两种常见的⽅法可以解决多个B+树访问同⼀套表数据的问题，⼀种叫做聚簇索引（clustered index ），⼀种叫做⾮聚簇索引（secondary index）。这两个名字虽然都叫做索引，但这并不是⼀种单独的索引类型，⽽是⼀种数据存储⽅式。对于聚簇索引存储来说，⾏数据和主键B+树存储在⼀起，辅助键B+树只存储辅助键和主键，主键和⾮主键B+树⼏乎是两种类型的树。对于⾮聚簇索引存储来说，主键B+树在叶⼦节点存储指向真正数据⾏的指针，⽽⾮主键。
InnoDB使⽤的是聚簇索引，将主键组织到⼀棵B+树中，⽽⾏数据就储存在叶⼦节点上，若使⽤”where id = 14″这样的条件查主键，则按照B+树的检索算法即可查到对应的叶节点，之后获得⾏数据。若对Name列进⾏条件搜索，则需要两个步骤：第⼀步在辅助索引B+树中检索Name，到达其叶⼦节点获取对应的主键。第⼆步使⽤主键在主索引B+树种再执⾏⼀次B+树检索操作，最终到达叶⼦节点即可获取整⾏数据。
MyISM使⽤的是⾮聚簇索引，⾮聚簇索引的两棵B+树看上去没什么不同，节点的结构完全⼀致只是存储的内容不同⽽已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独⽴的地⽅，这两颗B+树的叶⼦节点都使⽤⼀个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独⽴的，通过辅助键检索⽆需访问主键的索引树。
为了更形象说明这两种索引的区别，我们假想⼀个表如下图存储了4⾏数据。其中Id作为主索引，Name作为辅助索引。图⽰清晰的显⽰了聚簇索引和⾮聚簇索引的差异。
我们重点关注聚簇索引，看上去聚簇索引的效率明显要低于⾮聚簇索引，因为每次使⽤辅助索引检索都要经过两次B+树查，这不是多此⼀举吗？聚簇索引的优势在哪？
1 由于⾏数据和叶⼦节点存储在⼀起，这样主键和⾏数据是⼀起被载⼊内存的，到叶⼦节点就可以⽴刻将⾏数据返回了，如果按照主键Id 来组织数据，获得数据更快。
2 辅助索引使⽤主键作为”指针” ⽽不是使⽤地址值作为指针的好处是，减少了当出现⾏移动或者数据页分裂时辅助索引的维护⼯作，使⽤主键值当作指针会让辅助索引占⽤更多的空间，换来的好处是InnoDB在移动⾏时⽆须更新辅助索引中的这个”指针”。也就是说⾏的位置（实现中通过16K的Page来定位，后⾯会涉及）会随着数据库⾥数据的修改⽽发⽣变化（前⾯的B+树节点分裂以及Page的分裂），使⽤聚簇索引就可以保证不管这个主键B+树的节点如何变化，辅助索引树都不受影响。
3 Page结构
如果说前⾯的内容偏向于解释原理，那后⾯就开始涉及具体实现了。
理解InnoDB的实现不得不提Page结构，Page是整个InnoDB存储的最基本构件，也是InnoDB磁盘管理的最⼩单位，与数据库相关的所有内容都存储在这种Page结构⾥。Page分为⼏种类型，常见的页类型有数据页（B-tree Node）Undo页（Undo Log Page）系统页（System Page）事务数据页（Trans
action System Page）等。单个Page的⼤⼩是16K（编译宏UNIV_PAGE_SIZE控制），每个Page使⽤⼀个32位的int值来唯⼀标识，这也正好对应InnoDB最⼤64TB的存储容量（16Kib * 2^32 = 64Tib）。⼀个Page的基本结构如下图所⽰：
每个Page都有通⽤的头和尾，但是中部的内容根据Page的类型不同⽽发⽣变化。Page的头部⾥有我们关⼼的⼀些数据，下图把Page的头部详细信息显⽰出来：
我们重点关注和数据组织结构相关的字段：Page的头部保存了两个指针，分别指向前⼀个Page和后⼀个Page，头部还有Page的类型信息和⽤来唯⼀标识Page的编号。根据这两个指针我们很容易想象出Page链接起来就是⼀个双向链表的结构。
再看看Page的主体内容，我们主要关注⾏数据和索引的存储，他们都位于Page的User Records部分，User Records占据Page的⼤部分空间，User Records由⼀条⼀条的Record组成，每条记录代表索引树上的⼀个节点（⾮叶⼦节点和叶⼦节点）。在⼀个Page内部，单链表的头尾由固定内容的两条记录来表⽰，字符串形式的”Infimum”代表开头，”Supremum”代表结尾。这两个⽤来代表开头结尾的Record存储在System Records的段⾥，这个System Records和User Records是两个平⾏的段。InnoDB存在4种不同的Record，它们分别是1主键索引树⾮叶节点 2主键索引树叶⼦节点 3辅助键索引树⾮叶节点 4辅助键索引树叶⼦节点。这4种节点的Record格式有⼀些差异，但是它们都存储着Next指针指向下⼀个Record。后续我们会详细介绍这4种节点，现在只需要把Record当成⼀个存储了数据同时含有Next指针的单链表节点即可。
User Record在Page内以单链表的形式存在，最初数据是按照插⼊的先后顺序排列的，但是随着新数据的插⼊和旧数据的删除，数据物理顺序会变得混乱，但他们依然保持着逻辑上的先后顺序。
把User Record的组织形式和若⼲Page组合起来，就看到了稍微完整的形式。
现在看下如何定位⼀个Record：
1 通过根节点开始遍历⼀个索引的B+树，通过各层⾮叶⼦节点最终到达⼀个Page，这个Page⾥存放的都是叶⼦节点。
2 在Page内从”Infimum”节点开始遍历单链表（这种遍历往往会被优化），如果到该键则成功返回。如果记录到达了”supremum”，说明当前Page⾥没有合适的键，这时要借助Page的Next Page指针，跳转到下⼀个Page继续从”Infimum”开始逐个查。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。