mysql索引的数据结构，为什么用b+树

谈到索引，大家并不陌生。索引本身是一种数据结构，存在的目的主要是为了缩短数据检索的时间，最大程度减少磁盘 IO。

任何有数据的场景几乎都有索引，比如手机通讯录、文件系统（ext4\xfs\ntfs)、数据库系统（MySQL\Oracle）。数据库系统和文件系统一般都采用 B+ 树来存储索引信息，B+ 树兼顾写和读的性能，最极端时检索复杂度为 O(logN)，其中 N 指的是节点数量，logN 表示对磁盘 IO 扫描的总次数。

MySQL 支持的索引结构有四种：B+ 树，R 树，HASH，FULLTEXT。

B 树是一种多叉的 AVL 树。B-Tree 减少了 AVL 数的高度，增加了每个节点的 KEY 数量。

B 树的特性：（m 为阶数：结点的孩子个数最大值）

1. 树中每个节点最多含有 m 个孩子节点 (m>=2)；

2. 除根节点和叶子结点外，其他节点的孩子数量 >=ceil(m / 2)；

3. 若根节点不是叶子结点，最少有两个孩子

特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点；

4. 每个非叶子结点中包含有 n 个关键字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn) 其中：

Ki (i=1...n) 为关键字，且关键字按顺序升序排序 K(i-1)<Ki

Pi 为指向儿子节点的指针，且指针 P(i-1) 指向的儿子节点里所有关键字均小于 Ki，但都大于 K(i-1)

关键字的个数 n 必须满足：[ceil(m / 2)-1]<= n <= m-1

如果一个结点有 n 个关键字，那么该结点有 n+1 个分支。这 n+1 个关键字按照递增顺序排列

所有叶子结点都出现在同一层，是所有遍历的终点位置

B tree： 二叉树（Binary tree），每个节点只能存储一个数。

B-tree： B树（B-Tree，并不是B“减”树，横杠为连接符，容易被误导）

B树属于多叉树又名平衡多路查找树。每个节点可以多个数（由磁盘大小决定）。

B+tree 和 B*tree 都是 B-tree的变种

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O *** 作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。而B-/+/*Tree，经过改进可以有效的利用系统对磁盘的块读取特性，在读取相同磁盘块的同时，尽可能多的加载索引数据，来提高索引命中效率，从而达到减少磁盘IO的读取次数。

不了解磁盘相关知识的可以查看 硬盘基本知识（磁头、磁道、扇区、柱面）

下面通过示意图来看一下，B-tree、B+tree、B*tree

从图中可以看出，B-tree 利用了磁盘块的特性进行构建的树。每个磁盘块一个节点，每个节点包含了很关键字。把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

B-tree巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页（每页为4K），这样每个节点只需要一次I/O就可以完全载入。

B-tree 的数据可以存在任何节点中。

B+tree 是 B-tree 的变种，数据只能存储在叶子节点。

B+tree 是 B-tree 的变种，B+tree 数据只存储在叶子节点中。这样在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定

B*tree 每个磁盘块中又添加了对下一个磁盘块的引用。这样可以在当前磁盘块满时，不用扩容直接存储到下一个临近磁盘块中。当两个邻近的磁盘块都满时，这两个磁盘块各分出1/3的数据重新分配一个磁盘块，这样这三个磁盘块的数据都为2/3。

在B+树的基础上因其初始化的容量变大，使得节点空间使用率更高，而又存有兄弟节点的指针，可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少；

---