- 索引是帮助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
网友评论