理解MySQL的索引

• 索引是帮助MySQL高效获取数据的排好序的数据结构。
• 索引存储在文件里。（位置在数据库data文件下）

索引的结构

有如下几种被考虑过：
二叉树、红黑树、HASH、BTree、B+Tree

• 磁盘存储数据
  磁盘存储原理：磁盘旋转，磁头读取数据，磁头要移动到相应的扇区。
  磁盘上有很多磁道。
  寻道：磁头横向移动，寻找磁道，磁头移动速度慢，所以寻道速度慢。
  磁盘旋转：速度快。
  另外，从磁盘取一次数据到内存叫做一次IO。

• 二叉树：
  每个节点以Key-Value的形式，key存储值，value存数据在磁盘的地址，这样大大提高了查询效率，但是没有采用二叉树存储主要是因为，极端情况下，如果key一列是递增的，二叉树就变成单边增长的，没有提高效率。

  
  二叉树.png

• 红黑树：自动平衡的二叉树
  红黑树可以自动平衡，相比二叉树，不会出现单边增长的情况，但是如果数据很多，即便能够自动平衡，但是树的高度还是很高，因为红黑树是二叉树。

• B树

B树：在红黑树二叉平衡树的基础上，改成了多叉平衡树，
多叉树的节点能存储多少点，叫做度，如果度设置为4，那么一个节点能存储的点是15/16*4，也就是说，最后存储的节点可能是三个或四个。度可以是3~7。度增加了高度就小了。
但是度不可能设置无限大，这涉及到计算机的存储原理，计算机存储的最小单元是页，一页可以存储4k的数据，CPU、内存（RAM）、和磁盘交换数据都是以页为单位，一次交互可以拿一页或几页。所以为了一次性读取尽可能多的数据，把节点的大小设置为磁盘一次IO能取到数据的大小。一个节点大概是4页。
B树把数据和索引的点存储在一起。节点中的数据key从左到右递增排列，但是B树不支持范围查找。

B树.png

• B+ 树
  B+树把数据移到了叶子节点，可以大大增加非叶子节点的度，非叶子节点存储了冗余的索引。
  B+树在叶子节点增加了指针，指针实际上是双向的。这样可以支持范围查找。

  
  B+树.png
• Hash
  数据库底层也是有用 Hash 的，偶尔情况下会用。但是HASH不支持范围查找。因为 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

MySQL的两种存储引擎

存储引擎是表级别的。

• MyISAM
  MySIAM索引文件和数据文件是分离的。
  先从索引文件MYI中找到文件指针，再根据指针从MYD文件中找到数据行。
  主键索引与非主键索引（辅助索引）结构类似。

• InnoDB（聚集）
  数据文件本身就是索引文件。
  InnoDB存储表分为.frm和.ibd文件：ibd把数据和索引放在一起了。
  InnoDB的主键索引是把索引结构和数据存储在一起。
  这叫做聚集索引，也就是叶节点包含了完整的数据记录。
  主键最好用整型自增的主键，且InnoDB表必须有主键。必须有主键，如果没有，系统也会自动建一个默认的主键，因为InnoDB的非主键索引的叶子节点存储的Value是主键的索引（看下图）。整型是因为存储空间小，而且要经常进行比较，效率高。自增是因为，这样插入数据会往后插入，不用插入到前面已经满的节点中，也不用分叉，效率高。

  
  主键索引.png
  辅助索引.png

赋个链接：
可以查看一些数据结构，树的插入过程等。
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html