MySQL的索引原理

一、索引的本质解析

   推荐一个数据结构的演示网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
   索引： 是帮助MySQL高效获取数据的排好序的数据结构
   索引数据结构： 二叉查找树、红黑树、Hash表、B-Tree、B+Tree

   1、磁盘存储与内存存储

     磁盘存储 时，写入或读取的时间都会慢上许多，有时需要以秒计量
     内存存储 时，写入或读取的时间都非常之短，有时甚至可以忽略不计
       这也就是Redis诞生的原因之一

   2、MySQL数据的存储

     MySQL的数据是存储于 磁盘 之中的；在需要查询时，得要 逐行遍历 的查找；数据量大时，十分 耗时

   3、使用索引存储

     如：
       表结构与数据：

id	score
1	34
2	77
3	5
4	91
5	22
6	89
7	23

       查询语句：
         第一类： 以 score 建立索引

select * 
from t 
where score = 89

         第二类：以 id 建立索引

select * 
from t 
where id = 6

     1）二叉查找树存储

       第一类：以 score 建立索引

       第二类：以 id 建立索引
         弱化为了类链表结构；造成查询时，与无索引一样需要逐行遍历

       很明显，在第一类的情况下的确可以优化查询速度；但在第二类的情况下，是完全无法优化的

     2）红黑树存储

       第二类：以 id 建立索引
         通过红黑树单边节点大于2时，会自动向另一边进行平衡的特点，避免弱化成类链表的情况

       当索引是自增的，并且数量级达到千万级，那么红黑树的高度就会变得非常高，同样无法解决优化速率问题

     3）B-Tree存储

       通过每个节点中存放多个数据，对树的高度进行严格把控；至于每个节点存放多少数据，MySQL设定为了16KB

     4）B+Tree存储

       B+Tree是B-Tree的一个变形；也是MySQL中索引最大量使用的一种数据结构（另一个是Hash表结构）
       （1）降低每个节点中每个数据的大小（data），以保证一个节点能够存储更多的数据；
       （2）将所有的数据（data）都存放到叶子节点，以保证在内存中查找到之后无需再从磁盘中获取数据
       （3）每个叶子节点之间都由双向指针进行链接；以保证在需要进行区间查询时无需经过父节点
       （4）以树的数据结构（节点），是为了保证不一次性从磁盘中读取过多的数据，否则一样会导致速度极慢
       （5）整棵树的根节点从一开始就是存放在内存当中的，由于量不大，也就能够达到降低查询速度的效果

     5）Hash表存储

       对索引字段的数值进行一次Hash计算，得到Hash值；再将Hash值存放到另一张表（Hash表）中，Hash表中同时存放对应行的数据；再存储在磁盘当中
       Hash值在磁盘中能够一次性直接被查询到，故而会更加的快速
     但是：（1）过犹不及，当大量的数据需要存放时，全都需要进行Hash计算再存入Hash表中，反倒导致更慢
        （2）在进行区间查询时，就会更加复杂，速度非常之慢
     所以： MySQL中，存在着B+Tree数据结构索引和Hash表结构索引，但大多使用了B+Tree数据结构索引