为什么MySQL索引要用Btree，用就算了还这么快？

　　当你现在遇到了一条慢SQL需要进行优化时，你第一时间能想到的优化手段是什么？
　　大部分人第一反应可能都是添加索引，在大多数情况下面，索引能够将一条SQL语句的查询效率提高几个数量级。
　　索引的本质：用于快速查找记录的一种数据结构。
　　索引的常用数据结构：二叉树红黑树Hash表Btree（B树，并不叫什么B减树）Btree索引查询
　　大家知道selectfromtwherecol88这么一条SQL语句如果不走索引进行查找的话，正常地查就是全表扫描：从表的第一行记录开始逐行找，把每一行的col字段的值和88进行对比，这明显效率是很低的。
　　而如果走索引的话，查询的流程就完全不一样了（假设现在用一棵平衡二叉树数据结构存储我们的索引列）
　　此时该二叉树的存储结构（KeyValue）：Key就是索引字段的数据，Value就是索引所在行的磁盘文件地址。
　　当最后找到了88的时候，就可以把它的Value对应的磁盘文件地址拿出来，然后就直接去磁盘上去找这一行的数据，这时候的速度就会比全表扫描要快很多。
　　但实际上MySQL底层并没有用二叉树来存储索引数据，是用的Btree（B树）。为什么不采用二叉树
　　假设此时用普通二叉树记录id索引列，我们在每插入一行记录的同时还要维护二叉树索引字段。
　　此时找id7这一行记录时找了7次，和我们全表扫描也没什么很大区别。显而易见，二叉树对于这种依次递增的数据列其实是不适合作为索引的数据结构。为什么不采用Hash表
　　Hash表：一个快速搜索的数据结构，搜索的时间复杂度O（1）
　　Hash函数：将一个任意类型的key，可以转换成一个int类型的下标
　　假设此时用Hash表记录id索引列，我们在每插入一行记录的同时还要维护Hash表索引字段。
　　这时候开始查找id7的树节点仅找了1次，效率非常高了。
　　但MySQL的索引依然不采用能够精准定位的Hash表。因为它不适用于范围查询。为什么不采用红黑树
　　红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡；
　　若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。
　　假设此时用红黑树记录id索引列，我们在每插入一行记录的同时还要维护红黑树索引字段。
　　插入过程中会发现它与普通二叉树不同的是当一棵树的左右子树高度差1时，它会进行自旋操作，保持树的平衡。
　　这时候开始查找id7的树节点只找了3次，比所谓的普通二叉树还是要更快的。
　　但MySQL的索引依然不采用能够精确定位和范围查询都优秀的红黑树。
　　因为当MySQL数据量很大的时候，索引的体积也会很大，可能内存放不下，所以需要从磁盘上进行相关读写，如果树的层级太高，则读写磁盘的次数（IO交互）就会越多，性能就会越差。Btree
　　红黑树目前的唯一不足点就是树的高度不可控，所以现在我们的切入点就是树的高度。
　　目前一个节点是只分配了一个存储1个元素，如果要控制高度，我们就可以把一个节点分配的空间更大一点，让它横向存储多个元素，这个时候高度就可控了。这么个改造过程，就变成了Btree。
　　Btree是一颗绝对平衡的多路树。它的结构中还有两个概念
　　度（Degree）：一个节点拥有的子节点（子树）的数量。（有的地方是以度来说明Btree的，这里解释一下）
　　阶（order）：一个节点的子节点的最大个数。（通常用m表示）
　　关键字：数据索引。
　　一棵m借Btree是一棵平衡的m路搜索树。它可能是空树，或者满足以下特点：除根节点和叶子节点外，其它每个节点至少有m2lceildfrac｛m｝｛2｝rceil2m个子节点；m2lceildfrac｛m｝｛2｝rceil2m为m2然后向上取整每个非根节点所包含的关键字个数j满足：m2lceildfrac｛m｝｛2｝rceil2m1jm1；节点的关键字从左到右递增排列，有k个关键字的非叶子节点正好有（k1）个子节点；所有的叶子结点都位于同一层。名字取义（题外话，放松一下）
　　以下摘自维基百科
　　鲁道夫拜尔（RudolfBayer）和艾华M麦克雷（EdM。McCreight）于1972年在波音研究实验室（BoeingResearchLabs）工作室发明了Btree，但是他们没有解释B代表什么意义（如果有的话）。
　　道格拉斯科默尔（DouglasComer）解释说：两位作者从来都没解释过Btree的原始意义。我们可能觉得balanced，broad或bushy可能适合。其他人建议字母B代表Boeing。源自于他的赞助，不过，看起来把Btree当作Bayer树更合适些。
　　高德纳（DonaldKnuth）在他1980年5月发表的题为CS144CclassroomlectureaboutdiskstorageandBtrees的论文中推测了Btree的名字取义，提出B可能意味Boeing或者Bayer的名字。查找
　　Btree的查找其实和二叉树很相似：
　　二叉树是每个节点上有一个关键字和两个分支，Btree上每个节点有k个关键字和（k1）个分支。
　　二叉树的查找只考虑向左还是向右走，而Btree中需要由多个分支决定。
　　Btree的查找分两步：首先查找节点，由于Btree通常是在磁盘上存储的所以这步需要进行磁盘IO操作；查找关键字，当找到某个节点后将该节点读入内存中然后通过顺序或者折半查找来查找关键字。若没有找到关键字，则需要判断大小来找到合适的分支继续查找。操作流程
　　现在需要查找元素：88
　　第一次：磁盘IO
　　第二次：磁盘IO
　　第三次：磁盘IO
　　然后这有一次内存比对，分别跟70与88比对，最后找到88。
　　从查找过程中发现，Btree比对次数和磁盘IO的次数其实和二叉树相差不了多少，这么看来并没有什么优势。
　　但是仔细一看会发现，比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计。
　　另外Btree中一个节点中可以存放很多的关键字（个数由阶决定），相同数量的关键字在Btree中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。插入
　　当Btree要进行插入关键字时，都是直接找到叶子节点进行操作。根据要插入的关键字查找到待插入的叶子节点；因为一个节点的子节点的最大个数（阶）为m，所以需要判断当前节点关键字的个数是否小于（m1）。注：直接插入否：发生节点分裂，以节点的中间的关键字将该节点分为左右两部分，中间的关键字放到父节点中即可。操作流程
　　比如我们现在需要在MaxDegree（阶）为3的Btree插入元素：72查找待插入的叶子节点
　　节点分裂：本来应该和〔70，88〕在同一个磁盘块上，但是当一个节点有3个关键字的时候，它就有可能有4个子节点，就超过了我们所定义限制的最大度数3，所以此时必须进行分裂：以中间关键字为界将节点一分为二，产生一个新节点，并把中间关键字上移到父节点中。
　　Tip：当中间关键字有两个时，通常将左关键字进行上移分裂。删除
　　删除操作就会比查找和插入要麻烦一些，因为要被删除的关键字可能在叶子节点上，也可能不在，而且删除后还可能导致Btree的不平衡，又要进行合并、旋转等操作去保持整棵树的平衡。
　　随便拿棵树（5阶）举例子
　　情况一：直接删除叶子节点的元素
　　删除目标：50查找元素50位置
　　在〔36，50，63〕节点移除50后，依然符合Btree对节点内关键字的要求：m21关键字个数m15213151224
　　删除完成情况二：删除叶子节点的元素后合并旋转
　　删除目标：11查找元素11位置
　　在〔10，11〕节点移除11后，违背Btree对节点内关键字的要求：m21关键字个数m15212151214复制代码在它只剩1个关键字后，需要向兄弟节点借元素，这时候右兄弟有多的，它说：我愿意把14借给你但不可能让11和14放一起，因为1412，这时候就要进行旋转首先，将父节点的元素12移到该节点，然后12就让位给14
　　这整个过程就是删除叶子节点元素后的合并、旋转操作下面再来道菜
　　接着删除10在〔10，12〕节点移除10后，违背Btree对节点内关键字的要求在它只剩1个关键字后，需要向兄弟节点借元素，这时候没有兄弟有多的该怎么办呢首先，将父节点的元素8移到该节点，这时候3、6、8、12都小于14，就先把它们放一起
　　结果又发现父节点只剩个14了，它又违背了Btree对节点内关键字的要求，接着造！！！
　　首先，还是将父亲节点的元素20移到该节点，这时候根节点都直接没了，直接合并14、20、26、72关键字
　　在这整个过程包括删除叶子节点和非叶子节点的合并、旋转操作情况三：删除非叶子节点的元素后合并旋转
　　删除目标：12查找元素12位置
　　移除12后，违背Btree对节点内关键字的要求
　　对于非叶子节点元素的删除，我们需要用后继元素覆盖要被删除的元素，然后在后继元素所在的叶子中删除该后继元素。
　　最后呢我这里还有关于Java技术的资料那有需要的兄弟们可以私信我哟