共计 4788 个字符，预计需要花费 12 分钟才能阅读完成。
今天研究下，MySQL 中的 B -tree 索引，通过这篇文章你可以了解到，mysql 中的 btree 索引的原理，检索数据的过程，innodb 和 myisam 引擎中 btree 索引的不同，以及 btree 索引的好处和限制。
B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中 B -Tree 索引也同样是作为最主要的索引类型，这主要是因为 B -Tree 索引的存储结构在数据库的数据检索中有非常优异的表现，值得注意的是 mysql 中 innodb 和 myisam 引擎中的 B -tree 索引使用的是 B +tree（即每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历，并且除叶子节点外其他节点只存储键值和指针）。
一般来说，MySQL 中的 B-Tree 索引的物理文件大多都是以 B+tree 的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个 Leaf Node 上面出了存放索引键值和主键的相关信息之外，B+Tree 还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。
一：下面重点讲解下在 mysql 中 innodb 和 myisam 的 b -tree 索引的不同实现原理；
1）MyISAM 索引实现
MyISAM 引擎使用 B +Tree 作为索引结构，叶节点的 data 域仅仅存放的是指向数据记录的地址（也叫行指针），在 MyISAM 中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。
2）InnoDB 索引实现
虽然 InnoDB 也使用 B +Tree 作为索引结构，但具体实现方式却与 MyISAM 截然不同。
前面说过了，MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据行记录的地址（行指针）。但是在 innodb 引擎中，btree 索引分为两种，1，聚集索引（主键索引），2. 二级索引，或者说叫辅助索引。InnoDB 中的主键索引是聚集索引，表数据文件本身就是按 B +Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录（整行数据）。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主键索引。但是 innodb 的二级索引，保存的是索引列值以及指向主键的指针，所以我们使用覆盖索引的做优化处理就是针对 mysql 的 innodb 的索引而言的。
总结起来就是：
MyISAM 引擎中 leaf node 存储的内容:
主键索引：仅仅存储行指针；
二级索引：存储的也仅仅是行指针；
InnoDB 引擎中 leaf node 存储的内容
主键索引：聚集索引存储完整的数据（整行数据）
二级索引：存储索引列值 + 主键信息
下面这张图显示 mysql 中 innodb 和 myisam 引擎的索引实现的原理
二：接下来说下通过 btree 索引检索数据的过程：
myisam 和 innodb 引擎都是使用 B +tree 实现 btree 索引，检索数据的过程中，从根节点到子节点，然后找到叶子节点，接着找到叶子节点中存储的 data 的过程是一样的，只不过因为 myisam 和 innodb 引擎中的叶子节点中的 data 中存储的内容是不一样的（前文介绍了），所以找到叶子节点中的 data 之后再找真正数据的过程是不一样的，然后根据前文介绍的不同存储引擎中叶子节点 data 中存储的不同数据，例如 innodb 中的主键索引叶子节点存储的是完整数据行，所以根据 innodb 中的主键索引遍历数据时，找到了叶子节点的 data，就可以找到数据，至于 myisam 中叶子节点 data 存储的是行指针，也就是找到叶子节点的 data 后，再根据行指针去找到真正的数据行。
下面重点去说由根节点找叶子节点中的 data 域的过程：
为了对比，可以先看下 B -tree 实现原理：
B+tree 实现原理如下图：
通过两张图可以看出来，相对于 B -tree 来说，B+Tree 根节点和子节点只保存了键值和指针，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，这样可以大大加大每个节点存储的 key 值数量，降低 B +Tree 的高度，并且 B +Tree 中的叶子节点比 B -tree 多存储了指向下一个叶子节点的指针，这样更方便叶子节点的范围遍历。
每个节点占用一个磁盘块的磁盘空间，一个节点上有 n 个升序排序的关键字和（n+1) 个指向子树根节点的指针，这个指针存储的是子节点所在磁盘块的地址（注意这里的 n 是创建索引的时候，根据数据量计算出来的，如果数据量太大了，三层的可能就满足不了，就需要四层的 B +tree，或者更多层）, 然后 n 个关键字划分成（n+1) 个范围域，然后每个范围域对应一个指针，来指向子节点，子节点又从新根据关键字再次划分，然后指针指向叶子节点。
针对下图具体解释下 B +tree 索引的实现原理（修改自网络）：
针对上图，每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 17 和 35，P1 指针指向的子树的数据范围为小于 17，P2 指针指向的子树的数据范围为 17~35，P3 指针指向的子树的数据范围为大于 35。
然后针对上图模拟下 where id=29 的具体过程：（首先 mysql 读取数据是以块（page）为单位的）。
首先根据根节点找到磁盘块 1，读入内存。【磁盘 I / O 操作第 1 次】
比较关键字 29 在区间（17,35），找到磁盘块 1 的指针 P2。
根据 P2 指针找到磁盘块 3，读入内存。【磁盘 I / O 操作第 2 次】
比较关键字 29 在区间（26,30），找到磁盘块 3 的指针 P2。
根据 P2 指针找到磁盘块 8，读入内存。【磁盘 I / O 操作第 3 次】
在磁盘块 8 中的关键字列表中找到关键字 29。
分析上面过程，发现需要 3 次磁盘 I / O 操作，和 3 次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而 3 次磁盘 I / O 操作是影响整个 B -Tree 查找效率的决定因素。B-Tree 相对于 AVLTree 缩减了节点个数，使每次磁盘 I / O 取到内存的数据都发挥了作用，从而提高了查询效率。
相对于 B -tree 来说，B+Tree 根节点和子节点只保存了键值和指针，
查看 mysql 中的页的大小：
MySQL [meminfo]> show variables like ‘innodb_page_size’;
+——————+——-+
| Variable_name | Value |
+——————+——-+
| innodb_page_size | 16384 |
+——————+——-+
1 row in set (0.00 sec)
InnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT（占用 4 个字节）或 BIGINT（占用 8 个字节），指针类型也一般为 4 或 8 个字节，也就是说一个页（B+Tree 中的一个节点）中大概存储 16KB/(8B+8B)=1K 个键值（因为是估值，为方便计算，这里的 K 取值为〖10〗^3）。也就是说一个深度为 3 的 B +Tree 索引可以维护 10^3 * 10^3 * 10^3 = 10 亿 条记录。
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘 I / O 操作。
三：下面说下 mysql 中 innodb 引擎中聚簇表和 myisam 中非聚簇表的遍历数据的不同
如下图（来自网络）：
看上去聚簇索引的效率明显要低于非聚簇索引，因为每次使用辅助索引检索都要经过两次 B + 树查找，这不是多此一举吗？聚簇索引的优势在哪？
1 由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，如果按照主键 Id 来组织数据，获得数据更快。
2 辅助索引使用主键作为 ” 指针 ” 而不是使用行地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是 InnoDB 在移动行时无须更新辅助索引中的这个 ” 指针 ”，使用聚簇索引可以保证不管这个主键 B + 树的节点如何变化，辅助索引树都不受影响。
四：最后说下 mysql 中的 B +tree 索引的好处和限制（摘自高性能 mysql 第三版）
（一）可以使用的情况：
可以使用 btree 索引的查询类型，btree 索引使用用于全键值、键值范围、或者键前缀查找，其中键前缀查找只适合用于根据最左前缀的查找。前面示例中创建的多列索引对如下类型的查询有效：
1）全值匹配
全值匹配指的是和索引中的所有列进行匹配，即可用于查找姓名和出生日期
2）匹配最左前缀
如：只查找姓，即只使用索引的第一列
3）匹配列前缀
也可以只匹配某一列值的开头部分，如：匹配以 J 开头的姓的人（like ‘J%’)，这里也只是使用了索引的第一列，且是第一列的一部分
4）匹配范围值
如查找姓在 allen 和 barrymore 之间的人，这里也只使用了索引的第一列
5）精确匹配某一列并范围匹配另外一列
如查找所有姓为 allen，并且名字字母是 K 开头的，即，第一列 last_name 精确匹配，第二列 first_name 范围匹配
6）只访问索引的查询
btree 通常可以支持只访问索引的查询，即查询只需要访问索引，而无需访问数据行，即，这个就是覆盖索引的概念。需要访问的数据直接从索引中取得，这个是针对 innodb 中 btree 索引而言的。
因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的 order by 操作，一般来说，如果 btree 可以按照某种方式查找的值，那么也可以按照这种方式用于排序，所以，如果 order by 子句满足前面列出的几种查询类型，则这个索引也可以满足��应的排序需求。
(二）下面是关于 btree 索引的限制：
1）如果不是按照索引的最左列开始查找的，则无法使用索引 (注意，这里不是指的 where 条件的顺序，即 where 条件中，不管条件顺序如何，只要 where 中出现的列在多列索引中能够从最左开始连贯起来就能使用到多列索引)
2）不能跳过索引中的列，如创建了多列索引（姓，名，出生日期）：查询条件为姓和出生日期，跳过了名字列，这样，多列索引就只能使用到姓这一列。
3）如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查询，如：where last_name=xxx and first_name like‘xxx%’and dob=’xxx’; 这样，first_name 列可以使用索引，这列之后的 dob 列无法使用索引。
总结：mysql 中常用的引擎有 innodb 和 myisam, 这两个引擎中创建的默认索引都是 B -tree 索引，而都是 B +tree 结构实现的，并且 innodb 和 myisam 具体叶子节点存储的内容有所不同，然后覆盖索引是针对 innodb 引擎的索引而言的，因为 myisam 引擎中 b -tree 索引的叶子节点存储的仅仅是行指针。
本文永久更新链接地址 ：http://www.linuxidc.com/Linux/2018-01/150304.htm
