「MySQL高级篇」MySQL索引原理，设计原则( 二 ) _生活百科

BTREE 索引：最常见的索引类型，大部分索引都支持 B 树索引。
HASH 索引：只有Memory引擎支持，使用场景简单。
R-tree 索引（空间索引）：空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少，不做特别介绍。
Full-text （全文索引）：全文索引也是MyISAM的一个特殊索引类型，主要用于全文索引，InnoDB从Mysql5.6版本开始支持全文索引。

MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持
索引INNODB引擎MYISAM引擎MEMORY引擎BTREE索引支持支持支持HASH 索引不支持不支持支持R-tree 索引不支持支持不支持Full-text5.6版本之后支持支持不支持我们平常所说的索引，如果没有特别指明，都是指B+树（多路搜索树，并不一定是二叉的）结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用 B+tree 索引，统称为索引。
BTREE多路平衡搜索树，一棵m阶(m叉)BTREE满足：

每个节点最多m个孩子
- 孩子个数：ceil(m/2) 到 m
- 关键字个数：ceil(m/2)-1 到 m-1

ceil表示向上取整，ceil(2.3)=3

插入关键字案例

文章插图
保证不破坏m阶B树的性质由于3阶，最多只能2个节点，所以一开始26和30在一起，之后再来个85就要开始分裂了，30作为中间上位，26保持， 85去到右边即：中间位置上位，然后左边留在旧节点，右边去到新结点

如图中的70再插入的时候，70刚好是中间位置上位，然后62保持，85又去分一个新节点出来

文章插图
上位后又需要分裂

继续向上分裂即可，同理的

文章插图
相比优势相比二叉搜索树，高度/深度更低，自然查询效率更高。
B+TREE

B+树有两种类型的节点：内部结点（也称索引结点）和叶子结点。内部节点就是非叶子节点，内部节点不存储数据，只存储索引，数据都存储在叶子节点。
内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
父节点存有右孩子的第一个元素的索引。

文章插图
相比优势

B+Tree的查询效率更加稳定。由于B+Tree只有叶子节点保存key信息，查询任何key都要从root走到叶子，所以更稳定。
只需遍历叶子节点，就可以实现整棵树的遍历。

?
MySQL中的B+TreeMySql索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针(整体类似一个双向链表的结构)，就形成了带有顺序指针的B+Tree，提高区间访问的性能。?
细心的同学可以看出，这张图跟我们的二叉查找树简图的一个最大区别是什么？

从二叉查找树过渡到B树，有一个显著的变化就是，一个节点可以存储多个数据了，相当于一个磁盘块里边可以存储多个数据，大大减少了我们的 IO次数?。?/li>

MySQL中的 B+Tree 索引结构示意图：

文章插图
二叉查找树简图：

文章插图
索引原理BTree索引：

文章插图
初始化介绍浅蓝色的称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示)如磁盘块1包含数据项17和35，包含指针P1、P2、P3,P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。

真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99 。`
非叶子节点不存储真实的数据，只存储指引搜索方向的数据项，如17、35并不真实存在于数据表中。`

查找过程如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO 。在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO ， 29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中通过二分查找搜索到29 ，结束查询，总计三次IO 。真实的情况是，3层的B+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO ，显然成本非常非常高。