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

虽然增加了查询效率，但对于增删改，每次改动表，还需要更新一下索引

新增：自然需要在索引树中新增节点
删除：索引树中指向的记录可能会失效，意味着这棵索引树很多节点，都是失效的
改动：索引树中节点的指向可能需要改变

但实际上呢，我们MySQL中并不是用二叉查找树来存储，为何呢？

要知道，二叉查找树，此处一个节点只能存储一条数据，而一个节点呢，在MySQL里边又对应一个磁盘块，这样我们每次读取一个磁盘块，只能获取一条数据，效率特别的低，所以我们会想到采用B树这种结构来存储。
索引结构索引是在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的大小排列。
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
父节点存有右孩子的第一个元素的索引。