一、为什么使用B+树作为索引？

• InnoDB支持的常见的索引有：
• B+树索引
• 全文索引
• 哈希索引
• 其中B+树索引是InnoDB的默认索引，可参阅：https://blog.csdn.net/qq_41453285/article/details/104202458

Linux后台服务器开发交流/720209036

B-树的特点

一个M阶的B树具有如下几个特征：（如下图 M=3）(下文的关键字可以理解为有效数据，而不是单纯的索引)

定义任意非叶子结点最多只有 M 个儿子，且 M>2

根结点的儿子数为[2, M]除根结点以外的非叶子结点的儿子数为[M/2, M]，向上取整； (儿子数:[2,3])

非叶子结点的关键字个数=儿子数-1；(关键字=2)

所有叶子结点位于同一层

k 个关键字把节点拆成 k+1 段，分别指向 k+1 个儿子，同时满足查找树的大小关系。 (k=2)

有关B树的一些特性，注意与后面的B+树区分：

关键字集合分布在整棵树中

任何一个关键字出现且只出现在一个结点中

搜索有可能在非叶子节点结束

其搜索性能等价于在关键字全集内做一次二分查找；

B+树的特点：

B+树，是B树的一种变体，查询性能更好

m阶的B+树的特征：

有 n 棵子树的非叶子结点中含有 n 个关键字（b 树是 n-1 个），这些关键字不保存数据， 只用来索引，所有数据都保存在叶子节点（b 树是每个关键字都保存数据）

所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子 结点本身依关键字的大小自小而大顺序链接

所有的非叶子结点可以看成是索引部分，结点中仅含其子数中的最大（或最小）关键字

通常在 b+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点

同一个数字会在不同节点中重复出现，根节点的最大元素就是 b+树的最大元素

• 选用B+树作为数据库的索引结构的原因有：B+树的中间节点不保存数据，是纯索引。但是 B 树的中间节点是保存数据和索引的，相对来说，B+树磁盘也能容纳更多节点元素，更“矮胖”B+树查询必须查找到叶子节点，B树只要匹配到即可不用管元素位置，因此B+树查找更稳定（并不慢）对于范围查找来说，B+树只需遍历叶子节点链表即可，B树却需要重复地中序遍历，在项目中范围查找又很是常见的增删文件（节点）时，效率更高，因为 B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率
• 如果上面的图片看不懂，可以参阅另外一篇B-树与B+树的介绍文章：https://blog.csdn.net/qq_41453285/article/details/108023666

二、索引是如何实现的？

• 详情还可以参阅：https://blog.csdn.net/qq_41453285/article/details/104208974

B+树的大致工作原理

先抛开各种实现细节，来说一说B+树索引的大致工作原理

工作原理如下：

假设现在是主键索引表，一个表中有0、1、2、3、4、5、6、7、8八个主键

那么在B+树中，其叶子节点存储的是这些主键

当我们select * from table where id >1 and id <7的时候，那么会先从B+树的根节点开始向下查找，查找到1这个节点之后，由于底层节点之间是链表形式组织的，因此主键向右进行查找，从而查找到2、3、4、5、6这几个节点

insert、update、delete这些都是相同的原理

InnoDB和MyIASM的B+树之间有什么差别

InnoDB和MyIASM都支持B+树索引，那么它们之间的区别是什么呢？

InnoDB：其叶子节点存储不仅存储着主键的值，并且还存储着该主键对应的行数据。因此，其每个叶子节点=主键+整行数据值

MyIASM：其叶子节点也是存储着主键的值，但是其不存储该主键对应的行数据，其存储的是指向该行数据对应的地址。当我们查找到该主键值，再通过该指针查找到对应地址上的值

MyIASM与InnoDB通过B+数索引操作数据，哪一个更快？

规则为：

当操作的数据量不多时，可能两者没什么差别

当操作的数据量较大时，那么InnoDB比MyIASM快

解释如下：

InnoDB从磁盘读取数据在内存中构造一棵B+树，由于其B+树叶子节点存储的都是数据的值，因此其数据直接存储在内存中

MyIASM从磁盘读取数据在内存中构造一棵B+树，由于其B+树叶子节点只存储数据对应的指针，不存储值，因此其不会将数据读取都内存中

所以当数据量不多时，两者没什么区别：因为数据量小，InnoDB直接从内存中取数据，MyIASM通过指针去磁盘中查找数据，效率差别不大

当操作的数据量较大时，InnoDB直接从内存中取数据，那么速度较快，但是MyIASM需要不断的通过指针去磁盘中取数据，从而导致速度较慢

三、聚集索引与非聚集索引的区别是什么？

• 详情还可以参阅：https://blog.csdn.net/qq_41453285/article/details/104208974
• 下面我们以InnoDB存储引擎为例进行介绍
• B+树索引分为：聚集索引（clustered index）：按照每张表的主键构造一棵B+树，一个表只能有一个聚集索引非聚集索引（secondary index）：根据非主键构造B+树，一个表可以有多个辅助索引
• 不管是聚集还是非聚集索引，其内部都是B+树的，即高度平衡的，叶子节点存放着所有的数据
• 聚集索引与非聚集索引不同的是，叶子节点存放的是否为一整行的信息

聚集索引

InnoDB表数据文件本身就是一个索引结构，树的叶节点data域保存了完整的数据记录，这种索引叫做聚集索引

非聚集索引（辅助索引）

辅助索引（secondary index）也称为非聚集索引，叶子节点并不包含行记录的全部数据

叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉InnoDB存储引擎哪里可以找到与所以相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引键

InnoDB的所有辅助索引都引用主键作为data域。下图为定义在Col3上的一个辅助索引

辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主键索引中检索获得记录