首先我们来分析一下需求
MYSQL索引需要怎样的数据结构
为了防止数据因为特(duan)殊(kai)情(dian)况(yuan)丢失,我们的数据肯定是要持久化的,也就是保存在硬件(磁盘)里面,而我们知道 磁盘相对于内存来讲 速度要慢了几万倍 甚至即使万倍 所以我们必须减少磁盘的I/O操作
再有呢 我们知道MYSQL是支持单个查询和范围查询的 所以这个数据结构也需要单个查询和范围查询
所以总结一下 MYSQL数据结构需要
1.I/O操作尽可能少
2.支持高效的单个查询和范围查询
遍历
最暴力的方法肯定是遍历所有数据 很显然不行
二分查找
索引储存都是有序的 所以我们想到了二分查找(二分法不懂可以百度下 都有) 从遍历的O(n)时间复杂度减小到了O(logn)
不过这种一维的方法的插入非常麻烦 我们一旦插入或者删除数据 就要把它之后的所有数据往后移动一位....
二分查找树
为了解决插入费劲的问题 引入了二分查找树
我们把每个二分的节点往上拉 变成了一个树状结构
这个二分查找树的性质是 一个根节点总之比它的全部左节点大比他的全部右节点小
我们来看一下二分数组查找和二分数查找的对比 查7
二分数组 先取中间4 然后7>4 所以往右看 再去部分的中间 6 7>6 再往右看 找到了
二分查找树 4->6->7
他俩本质上是一样的
但是插入就不一样了
我们想插个3.5进去 二分数组的话 就得找到3和4之间的位置 然后把4567往后移动 然后再放进去
二分查找树 贼方便了就 直接大于3 小于4是吧 我直接给你挂3底下
太好了 这直接用二分查找树 无敌了
啊不行 假如我们还是用这个树举例 我再插入3.51 3.52 3.53 3.54 3.55.............(此处省略一万个数据)
3.5在挂在3底下 3.51挂在3.5下面 3.52挂在3.51底下............
它就会一直在3右边的分支垒上去 一直插的话 就退化成链表了
由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作（假设一个节点的大小「小于」操作系统的最小读写单位块的大小），也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。
二叉查找树由于存在退化成链表的可能性，会使得查询操作的时间复杂度从 O(logn) 升为 O(n)。
而且会随着插入的元素越多，树的高度也变高，意味着需要磁盘 IO 操作的次数就越多，这样导致查询性能严重下降，再加上不能范围查询，所以不适合作为数据库的索引结构。
自平衡二叉树
为了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出平衡二叉查找树（AVL 树）。
主要是在二叉查找树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。(通过左选右选操作维持左树右树平衡性 原理较复杂不在这里深究)
不过呢即使是平衡二叉查找树，也会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。
但是我们也有一点改进的思路 二叉树高度比较高 那么三叉树就可以有效的降低高度 那多叉树还会远吗
B 树
为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。
B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。
假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1个）数据和最多有 3 个（M个）子节点，超过这些要求的话，就会分裂节点,like this
我们来看一下三阶B树
假设我们在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步：
- 与根节点的索引(4，8）进行比较，9 大于 8，那么往右边的子节点走；
- 然后该子节点的索引为（10，12），因为 9 小于 10，所以会往该节点的左边子节点走；
- 走到索引为9的节点，然后我们找到了索引值 9 的节点。
可以看到，一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3 ，所以在查询过程中会发生 3 次磁盘 I/O 操作。
而如果同样的节点数量在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。
但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。
而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。
另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降
B+树
这一眼就知道这是B树的升级强化版 那么它是怎么进行升级的呢
B+ 树与 B 树差异的点，主要是以下这几点：
- 叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
- 所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
- 非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
- 非叶子节点中有多少个子节点，就有多少个索引；
可以看到每个父节点就会把叶节点分成几份方便查询 这样分下去其实还是保留了一部分最开始的二分思想的
哎你说人这脑瓜子咋长的呢 我看人家的解析理解都费劲 咋创造出来的呢
单点查询
B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。
但是 B 树的查询波动会比较大，因为每个节点即存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。
B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。
插入和删除效率
B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快，
但是B树删除一个节点却非常麻烦,删掉一个节点可能导致整个树形的变化
因此B+的删除 插入效率较高
范围查询
B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。
因为 B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助，比如说我们想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。
而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。
因此，存在大量范围检索的场景，适合使用 B+树，比如数据库。而对于大量的单个索引查询的场景，可以考虑 B 树，比如 nosql 的MongoDB
