今天上午11点，仅99套，先到先得！
文章来源：
目录前言
那么多数据结构，为什么选树结构？
那么多的树结构？为什么偏偏采用B+树作为索引？
总结
前言
为什么MySQL采用B+树作为索引？
如果纯粹的猜测MySQL数据库索引为什么使用B+树？那么围绕这个问题的回答通常一定是围绕B+树本身是什么，有什么优势这两点去解释这个问题。
这不是我开始这么去想的，看了很多文章都是从这一维度问答，这些回答让我失望啊。直到那天问了坐在我旁边那个整天摸鱼的5年程序员；他慵懒的回答：你想为什么是使用的是树结构呢？咦，听到这回答，一下打开了我的思绪，有点意思！
先抛开B+树是什么，有什么优势，这些先入为主的答案。（我并不想要这个往我脑袋硬塞的硬邦邦的答案。）
我想要的是为什么？为什么MySQL的索引有那么多的数据结构可选，偏偏选树结构？为什么那么多的树结构？为什么又偏偏采用B+树作为索引？
这才是我要想明白的！我想要的是不只是答案还要答案背后的脉络！我想要的不仅是要知其然，更想要知其所以然。
那么多数据结构，为什么选树结构？
众多的数据结构在逻辑层面可分为：线性结构和非线性结构。
线性结构有：数组、链表，基于它们衍生出的有哈希表（哈希表也称散列表）、栈、队列等。
非线性结构有：树、图。
还有其他数据结构如：跳表、位图也都由基础数据结构演化而来，不同的数据结构存在即都是为了解决某些场景问题。
如果要知道索引适合什么数据结构，那我们索引需要来解决什么样的问题（痛点）和需要发挥着什么样的作用，其次再看用什么样的数据结构；后者只是果，前者才是因。
MySQL存储的数据是在磁盘里，因为即使设备断电，放在磁盘的数据是不会有影响的，保障了数据不丢失，这意味着MySQL在磁盘上的数据是持久化的。
但数据存储在磁盘得到保障的同时也是有代价的，这代价就是磁盘的处理速度是毫秒级别的，相比内存纳秒级别的速度，简直是小巫见大巫。
你可能对时间单位没什么概念，可以看1毫秒能慢上纳秒几万倍。
索引虽然存储在磁盘上，但使用索引查找数据时，可以从磁盘先读取索引放到内存中，再通过索引从磁盘找到数据；再然后将磁盘读取到的数据也放到内存里。
索引就让磁盘和内存强强联手，趁机搭上了内存的车，感受了一把纳秒级别速度的推背感。
但是不管查询的过程中怎么优化，只要根还在磁盘，就避免不了会发生多次磁盘I/O，而磁盘I/O次数越多，消耗的时间也越多。（聪明的同学这会可以看出这其实就是个需要考虑解决的痛点了）
要尽少在磁盘做I/O操作：但还有那么多的数据结构可选呢？其实索引的需要发挥的目的已经决定了有哪些数据结构可选，那么就可以缩小选择其他数据结构的范围。从为什么要建索引本身的首要目的出发。
要能尽快的按照区间高效地范围查找：当然是除了首要目的能支持高效范围查询，还能有插入更新等操作的动态数据结构。
所以有满足以这两条主要条件的除了树结构你还会想到其他什么数据结构？那就是哈希表、跳表。
哈希表
先看哈希表，哈希表对于我们来说太熟悉不过，哈希表的物理存储是一个数组，而数组在内存中是连续地址的空间。
数据以Ky、Valu的方式存储。哈希表拥有精确的查询，所以时间复杂度是O(1)。
而哈希表之所以能这么快是通过Ky计算数组下标来快速找到Valu。
最简单的计算的方式是余数法，通过先计算ky的HashCod，再通过哈希表的数组长度对HashCod求余，求余得出的余数就是数组下标，最后由下标访问到哈希表中存的Ky、Valu。
但是Ky计算出的下标可能会有相同的情况，例如HashCod对6取余是2，但是HashCod对6取余也是2。
哈希算法随机计算出HashCod取余数组长度可能出现数组下标相同的情况，就是所谓的哈希冲突。
而哈希冲突常用链表的方法解决。当发生哈希冲突，相同下标的数据元素会替换成存储指针，而不同Ky的数据元素添加到链表中。查找时通过指针遍历这个链表，再匹配出正确的Ky就可以。如上图所示，Ky是"一颗剽悍的种子"的字符串，Valu是"不要忘了