4 MySQL学习---MySQL索引( 三 ) _生活百科

若根节点不是叶子节点，则至少有2个子节点

所有的叶子结点都在同一层

每个非叶子节点由n个键和n+1个指针组成，其中[ceil(m/2)-1]<=n<=m-1

B树的主要特点如下：

B树的节点中存储着多个元素，每个内节点有多个分叉。
节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，所有的节点中都储存数据。
父节点当中的元素不会出现在子节点中。
所有的叶子结点都位于同一层，叶节点具有相同的深度，且彼此之间没有指针连接。

B树的简图如下图所示：
【4 MySQL学习---MySQL索引】

文章插图
注：这里限于篇幅，不再详解B树的插入和删除操作，感兴趣可到MySQL学习(5)---B树和B+树详解查看。
应该说，B树已经接近数据库对底层数据结构的要求了，但仍有可以优化的地方。如：

B树不支持范围查询的快速查找，因为它采取了中序遍历的方式。以上图为例，我们要查询2~9之间的数据，在查找到2之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
如果data域中存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B+树的引入B+树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B+树结构构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。

B树：非叶子节点（包括根节点）和叶子节点都会存储数据。

B+树：只有叶子节点才会存储数据，非叶子节点只存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

B+树的简图如下所示：

文章插图
B+树的特征：

有m个子节点的中间节点最多包含m个键（B树中是m-1个键），每个键不保存数据，只用来存储索引。
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息）

B+树的优势：

由于叶子节点上存放了所有的数据，并且有指针相连，每个叶子节点在逻辑上是相连的，所以对于范围查找比较友好。
B+树的所有数据都在叶子节点上，所以B+树的查询效率稳定，一般都是查询3次。
B+树有利于磁盘的IO，因为他的层高基本不会因为数据扩大而增高。（三层树结构大概可以存放2000万数据量）

为什么说B+树比B树更适合数据库索引？（1）B+树的磁盘读写代价更低
树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一磁盘块中，那么磁盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
（2）B+树查询效率更加稳定
B树搜索在非叶子节点还是叶子节点结束都有可能，越靠近根节点，查找效率越快；而B+树无论查找的是什么数据，最终都需要从根节点一直走向叶节点，所有查找所经过的次数都是一样的，导致每一个数据的查询效率相当。
（3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）
B树在提高了IO性能的同时并没有解决元素遍历效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。
补充：B树的范围查找采用中序遍历，而B+树采用在双向链表上遍历的方式。
索引分类可以查看官网文档，看看MySQL存储引擎支持的索引类型。官网文档：https://dev.mysql.com/doc/refman/8.0/en/create-index.html
下图是MySQLinnoDB、MYISAM、MEMORY、RDB存储引擎对各种索引类型的支持情况。

由于本文是基于MySQL的innoDB存储引擎，所以重点观察第一个表格。
由于本文是基于MySQL的InnoDB存储引擎，因此重点观察第一个表格，其他的表格可以自行观看。从表格中可以看出， InnoDB存储引擎索引只支持BTREE类型的索引，索引的类别有Primary Key，Unique，Key ， FULLTEXT和SPATIAL 。