MySQL索引数据结构红⿊树，Hash，B+树详解
⼀、MySQL索引底层的实现
索引是帮助MySQL⾼效获取数据的排好序的数据结构；
上图中有⼀张表，表名为 t ，表中有7条数据；使⽤select * from t where t.clo2 = 89 查询；
1、若表中没有创建索引，则会全表扫描，⼀条⼀条的遍历查询，需要遍历 6 次，查询⼀⾏数据⾄少和磁盘做⼀次I/O操作（I/O是很耗性能的），⾄少要做 6 次 I/O 操作；
2、表中建⽴了索引：
（1）若索引底层是⼆叉树（左边的⼦元素⼩于⽗元素，右边的⼦元素⼤于⽗元素）存储的，则如下图所⽰：
这样查询 4 次就到数据了；
当然，在极端情况下，若按照⼤⼩顺序插⼊⼆叉树，则会形成单边增长的⼆叉树，这样使⽤索引的时候和全表扫描是⼀样的了；
（2）若索引底层是红⿊树存储的，则如下图所⽰：
红⿊树：当单边的节点⼤于3时候，就会⾃动调整，这样可以解决⼆叉树的弊端；红⿊树也叫平衡⼆叉树；
当然，红⿊树也有弊端的，当数据量特别⼤的时候，红⿊树的⾼度特别⼤；假如有500W条数据，则红⿊树⾼度为 23，若我们要查的刚好是红⿊树的叶⼦节点，则需要查 23 次才可以，即要发⽣ 23 次的磁盘 I/O 操作，性能就太差了；
（3）若索引底层是 B-Tree存储的
（叶⼦节点具有相同的深度，叶节点的指针为空；所有索引元素不重复；⼀个节点可以存储多个元素，节点中的数据索引从左到右递增排列）
若 Max. Degree = 4，则如下图所⽰：
这样只查询 2 次就到了；
当然 B-Tree 也是有弊端的；以下是 B-Tree 的存储，数字为key，data为对应的数据；
若⼀个节点我们申请的空间为16KB，若data中的数据过⼤，则⼀个节点能放的数据量越⼩，这样就会造成树的⾼度⽐较⼤了（⽐红⿊树⾼度⼩点）；
（4）MySQL的索引底层使⽤的 B+Tree存储的（数据存储在叶⼦节点）
B+Tree：
  ⾮叶⼦节点不存储data，只存储索引（冗余），可以放更多索引；
  叶⼦节点包含所有索引字段，即所有的data元素存储在叶⼦节点上；
  叶⼦节点使⽤指针连接，提⾼区间访问的性能；
  从左到右⼀次递增;
B+Tree 相对于 B-Tree的优化点：
优化点1：  B-Tree的所有节点都存储了 data 元素， B+Tree的⾮叶⼦节点不存储 data元素，则 B+Tree 的⼀个⾮叶⼦节点可以存储更多的索引；
优化点2： B+Tree在叶⼦节点之间增加了指针连接；对 select * from t where col2 > 20 的范围查有很好的⽀持；
MySQL 对 B+Tree 做了优化，叶⼦节点使⽤的是双向指针；
以上图中查 49 的数据：
I. 先将根节点的数据(15, 56, 77) 做⼀次磁盘 I/O 操作取出加载到内存中，然后再在内存中做⽐对，到对应的指针，查到其对应的节点；
II. 将指针指向节点的数据(15, 20, 49) 做⼀次磁盘 I/O 操作取出加载到内存中，然后再在内存中做⽐对，到对应的指针，接着去叶⼦节点获取数据；
<1> 查看MySQL⽂件页⼤⼩（⼀个节点的⼤⼩）：
SHOW GLOBAL STATUS like 'Innodb_page_size'；
<2> MySQL页⽂件默认为16KB，树的⾼度为3，能够存储多少数据？
  我们先看⾮叶⼦节点，假设主键ID为 bigint 类型，那么长度为8B，指针⼤⼩在Innodb源码中6B，⼀共
14B，那么⼀页（即⼀个节点）可以存储  16KB/14B=1170 个索引元素和 1170个指针；根节点有1170个索引和1170个指针，树⾼度为2的节点就有1170个，那么叶⼦节点的数量为 1170x1170；每个叶⼦节点可以存储16KB，若每条数据⽐较⼤为1KB，那么每个叶⼦节点可以存储16条数据；那么，⾼度为3的B+Tree 的叶⼦节点可以存储的数据量为 1170x1170x16=2000W；
在实际的MySQL中表的索引存储可以选择 Hash 或 BTree
（5）若索引使⽤的 Hash 存储的，存储的时候先做⼀次hash运算，根据 hash 的值就可以快速的定位数据的磁盘指针，这样就不管表⾥⾯有多少数据，我们的查询效率都⾮常的快；
在实际中为什么使⽤ B-Tree 或 B+Tree 来存储索引的⽅式更多，⽽不太使⽤ hash 呢？
原因1：若使⽤ select * from t where clo2 > 6，这种查范围的SQL，那Hash就不能搞定了，就不会⾛索引了；⽽且对排序hash也没有办法；
原因2：hash会产⽣ hash 碰撞，MySQL的底层对hash做了处理，很少会发⽣hash碰撞的；
⼆、MySQL的存储引擎的实现
同⼀个数据库中，不同的表可以设置不同的存储引擎；
MySQL的数据存储在 data ⽬录下， data ⽬录下的⽂件夹是以数据库为单位的，数据库⽂件夹下⾯存放的表数据；  data / {数据库名} /表⽂件
1、MyISAM存储引擎索引实现
MyISAM存储引擎的索引⽂件和数据⽂件是分离的（⾮聚集）；
MyISAM 存储引擎的⼀个表有3个⽂件：  *.frm ⽂件存储的表的结构； *.MYD ⽂件存储表的数据； *.MYI ⽂件存储表中的索引数据；MYISAM 存储引擎的索引的叶⼦节点的data中存储的是索引所在⾏的磁盘指针； ---- ⾮聚集索引
MYISAM 存储引擎的主键索引和⾮主键索引的存储是差不多的，InnoDB 存储引擎的主键索引和⾮主键索引存储是不⼀样的；
2、InnoDB 存储引擎-索引实现
InnoDB存储引擎索引⽂件和数据⽂件是合⼀的(聚集)；
查看mysql索引InnoDB 存储引擎的1个表有2个⽂件：  *.frm ⽂件存储表的结构； *.ibd ⽂件存储的是索引和数据；
InnoDB表的数据⽂件本⾝就是按 B+Tree 组织的⼀个索引结构⽂件；聚集索引叶⼦节点包含了完整的数据记录；
（1）InnoDB的主键索引
InnoDB 存储引擎的索引的叶⼦节点的data中存储的是索引对应的所有数据；----聚集
问题1：为什么InnoDB表必须有主键，并且推荐使⽤整型的⾃增主键？
a. 因为 MySQL对于 InnoDB 表设计的就是按照 B+Tree 组织存储数据的，若没有主键就没有办法去存储数据了；但是在平常我们建表的时候没有指定主键也是可以建成功的，这是因为 MySQL 会⽣成⼀个 rowid 作为数据的唯⼀标识；
b. 若使⽤的 UUID 作为主键，在查的时候需要去⽐较⼤⼩，字符串UUID⽐较的效率肯定低于数据的⽐较；在进⾏⽐较的时候会把数据拿到内存空间中做⽐较，UUID为字符串占⽤的内存空间就会较多；
c. 若是递增的，则插⼊的数据直接向后排，这个节点满了，直接新增⼀个节点就好了；若不是递增的，有个节点存储满了（5, 9），但是新插⼊了⼀个数据（7）在这个节数据的中间，则需要将这个节点先分裂，再平衡去满⾜ B+Tree 的结构；
（2）InnoDB 的⾮主键索引
在使⽤⾮主键索引查的时候，先从⾮主键索引的树中查询到对应的主键值，然后使⽤主键值去到主键索引的树中去查；
对于⾮主键单值索引，若索引字段的值为 null，则它的数据不会放到⾮叶⼦节点上，是放在叶⼦节点的链表的最前⾯的；（强烈不建议字段设置为null）
问题2：为什么⾮主键索引结构叶⼦节点存储的是主键值？（⼀致性和节省存储空间）
因为在插⼊数据之前先要维护⼀下索引，然后再将数据插⼊进去；若主键索引和⾮主键索引的叶⼦节点都存储具体的数据，则⼀个 insert 语句插⼊成功的判断就是向主键索引中插⼊成功且向⾮主键索引中也插⼊成功，这样就造成了事务的问题，事务是很耗性能的；当然，主键索引和⾮主键索引的叶⼦节点都存储具体数据，会造成数据的同样的数据存储了⼏份，就造成了空间的浪费；
联合索引的底层存储结构
以上的联合索引从左到右由字段 a，b，c 组成；
联合索引在存数据或⽐较的时候，先⽐较联合索引最前⾯的字段，若最前⾯的字段值⼀样，则再⽐较第⼆个字段的值；
联合索引的索引字段中有⼀个值为null，则将其放在叶⼦节点的最前⾯；可以认为null值是最⼩的。