MYSQL数据库为什么使用B+Tree作为索引的数据结构？
二叉树为什么不行
二叉树的查找时间复杂度可以打到O(log2(n))。下图为二叉树的存储结构
二叉树搜索相当于一个二分查找。二叉查找能打打提升查询的效率，但是他有一个问题：二叉树以第一个插入的数据作为根节点，如上图中，如果只看右侧，就会发现，就是一个线性链表结构。如果我们现在的数据包含1,2,3,4，就回出现以下情况
如果我们要查询的数据为4，则需要遍历所有的节点才能找到4，即，相当于全表查询，就是由于存在这种问题，所以二叉查找树不适合用于作为索引的数据结构
平衡二叉树为什么不可行
为了解决二叉树存在的线性链表问题，会想到使用平衡二叉查找树来解决。下图为平衡二叉树：
平衡二叉查找树定义为：节点的子节点高度差不能超过1，如上图中的节点20，左节点高度为1，有节点高度为0，差为1，所以上图没有违反定义，它就是一个平衡二叉树。保证二叉树平衡的方式为左旋，右旋等操作。
如果上图中平衡二叉树保存的是id索引，现在要查找id=8的数据，过程如下
1.把根节点加载进内存，用8和10进行比较，发现8比10小，继续加载10的左子树。 2.把5加载进内存，用8和5比较，同理，加载5节点的右子树。 3.此时发现命中，则读取id为8的索引对应数据。
索引保存数据的方式一般有两种
数据区保存id 对应行数据的所有数据具体内容。 数据区保存的真正保存数据的磁盘地址。
到这里，平衡二叉树解决了存在现行链表的问题，数据查询的效率也还可以，基本能达到O(long2(n))，那为什么mysql不选择平衡二叉树作为索引存储结构，他又存在什么样的问题呢？
搜索效率不足。一般来说，在树结构中，数据所处的深度，决定了搜索时的IO次数（MySQL中将每个节点大小设置为一页大小，一次IO读取一页/一个节点）。如上图中搜索id = 8的数据，需要进行三次IO。当数据量到达几百万的时候，树的高度就会很恐怖。
查询不稳定。如果查询的数据落在根节点，只需要一次IO，如果是叶子节点或者是支节点，会需要多次IO才可以。
存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO的预读能力。因为操作系统和磁盘之间一次数据交换是以页为单位的，一页大小为4K，即每次IO操作系统会将4K数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能填满4K的内容。辛辛苦苦做了一次IO操作，却只加载了一个关键字。在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次 的IO。
有没有一种结构能够解决二叉树这种问题--多路平衡查找树
多路平衡查找树（Balance Tree）
B Tree 是一个绝对平衡术，所有的叶子节点都在同意高度，如下图所示：
上图为一个2-3树（每个节点存储2个关键字，有3路），多路平衡查找树也就是多叉的意思，从上图中可以看出，每个节点保存的关键字的个数和路数关系为：关键字个数=路数-1 。
假设要从上图中查找id = x的数据，B TREE 搜索过程如下：
去除根磁盘块，加载40和60两个关键字。
如果X等于40，则命中；如果X小于40走P1；如果40 < X < 60走P2；如果X=60则命中；如果X大于60走P3。
根据以上规则命中后，接下来加载对应的数据，数据区中存储的是具体的数据或者是指向数据的指针。
为什么说这种结构能解决平衡二叉树存在的问题呢？
B Tree能够很好的利用操作系统和磁盘的交互特性，MySQL为了很好的利用磁盘的预读能力，将页的大小设置为16K，即将一个节点（磁盘块）的大小设置为16K，一IO将一个节点内容加载进内存。这里，假设关键字类型为int，即4字节，若每个关键字对应的数据区也为4字节，不考虑子节点引用的情况下，则上图中每个节点大约能够存储（16*1000）/8 = 2000个关键字，共2001个路数。对于二叉树，三层高度，最多可以保存7个关键字，而对于这种有2001路的B树，三层高度能够搜索的关键字个数远远大于二叉树。
在B树保证树的平衡的过程中，每次关键字的变化，都会导致结构发生很大的变化，这个过程特别浪费时间，所以创建索引一定要创建合适的索引，而不是把所有的字段都创建索引，创建冗余索引只会对数据进行新增，删除，修改时增加性能消耗。
B+ Tree
B+ Tree是B Tree的一个变种，在B+ Tree中，B树的路数和关键字的个数的关系不再成立了，数据检索规则采用的是左闭合区间，路数和关键个数关系为1：1，具体如下图：
如果上图中是用ID做的索引，如果是搜索x = 1的数据，搜索规则如下：
去除根磁盘块，加载1,28,66三个关键字。
x<=1 走P，去除磁盘块， 加载1， 10， 20三个关键字。
x<=1走P1，去除磁盘块， 加载1， 8， 9三个关键字。
已经达到叶子节点，命中1，接下来加载对应的数据，途中数据区中存储的是具体的数据。
B树和B+树的区别是什么？
B+Tree关键字的搜索采用左闭合区间，之所以采用左闭合区间是因为他要最好的去支持自增id，这也是mysql的设计初衷。即，如果id = 1命中，会继续往下查找，直到找到叶子节点中的1 。
B+Tree根节点和支节点没有数据区，关键字对应的数据只保存在叶子节点中。即只有叶子节点中的关键字数据区才会保存真正的数据内容或者是内容的地址。而在BTree中，如果根节点命中，则会直接返回数据。
3.在B+Tree中，叶子节点不会去保存子节点的引用。
4.B+Tree叶子节点是顺序排序的，并且相邻的节点具有顺序索引的关系，如上图中叶子节点之间有指针相连接。
MySQL为什么使用B+Tree
B+Tree是B Tree的变种，B Tree能解决的问题，B+ Tree也能够解决（降低树的高度，增大节点存储数据量）。
B+ Tree扫库和扫表能力更强。如果我们要根据索引去进行数据表的扫描，对B Tree进行扫描，需要把整个树遍历一遍，而B+Tree只需要遍历他的所有叶子节点即可（叶子节点之间有引用）。
B+ Tree磁盘读写能力更强。他的根节点和支节点不保存数据区，所以根节点和支节点同样大小的情况下，保存的关键字要比B Tree要多。而叶子节点不保存子节点引用，能用于保存更多的关键字和数据。所以，B+ Tree读写一磁盘加载的关键字比 B Tree更多。
B+Tree排序能力更强。上面的图中可以看出，B+ Tree天然具有排序功能。
B+ Tree查询性能稳定。B+ Tree数据只保存在叶子节点中，每次查询数据，查询IO次数一定是稳定的。当然这个每个人的理解都不同，因为在B Tree如果根节点命中直接返回，确实效率更高。
MySQL B+Tree落地形式
- MYISAM存储引擎存储数据库数据，一共有三个文件
- Frm：表的定义文件。
- MYD：数据文件，所有的数据保存在这个文件中。
- MYI：索引文件。
- InnoDB存储引擎存储数据库数据，一共有两个文件（没有专门保存数据的文件）
- Frm文件：表的定义文件。
- lbd文件：数据和索引存储文件。数据以主键进行聚集存储，把真正的数据保存在叶子节点中。
MyISAM存储引擎
在MYISAM存储引擎中，数据和索引的关系如下：
如何查找数据：
如果要查询id = 40的数据：先根据MyISAM索引文件去找id = 40的节点，通过这个节点的数据区拿到真正保存数据的磁盘地址，在通过这个地址从MYD数据文件中加载对应的记录。
如果有多个索引，表现形式如下：
所以在MYISAM存储引擎中，主键索引和辅助索引是同级别的，没有主次之分。
InnoDB存储引擎
InnoDB主键索引为聚集索引，即数据库表行中数据的物理顺序和键值的逻辑顺序相同。
InnoDB以主键索引来聚集组织数据的存储，下面看看InnoDB是如何组织数据的
如上图中，叶子节点的数据区保存的就是真实的数据，在通过索引进行检索的时候，命中叶子节点，就可以直接从叶子节点中取出行数据。mysql5.5版本之前默认采用的是MyISAM引擎，之后用的InnoDB引擎。
在InnoDB中，辅助索引的格式如下图所示：
如上图，主键索引的叶子节点保存的是真正的数据。而辅助索引叶子节点的数据区保存的是关键索引关键字的值。
加入要查询name = c 的数据，其搜索过程如下：
- 现在辅助索引中通过c查询最后找到主键id = 9 。
2.在主键索引中搜索id为9的数据，最终在主键索引的叶子节点中获取到真正的数据。
所以通过副主索引进行检索，需要进行两次索引检索，
之所以这样设计，一个原因就是：如果和MyISAM一样在主键索引和辅助索引的叶子节点中都芬芳数据行指针，一单数据发生迁移，则需要去重新维护所有的索引。
把InnoDB和MyISAM区别放在同一张图中看，就如下所示
创建索引的几大原则
列的离散型
离散型的计算公式：count(distinct column_name):count(*),就是用去重后的列值个数比个数，值在(0,1]方位内。离散型越高，选择型越好。
如下表中各个字段，明显能看出Id的选择性比gender更高。
为什么离散型越高，选择性越好：
因为离散度越高，通过索引最终确定的范围越小，最终扫描的行数也就越少。
京公网安备 11010502036488号