mysql 索引
索引是帮助Mysql高效获取数据的而且已经是排好序的数据结构
索引数据结构一般有以下几种：
- 二叉树
- 红黑树
- hash表
- B(+)Tree
推荐一个外国的网站学习数据结构：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
红黑树相较于二叉树，可以自动旋转至左右子树平衡，高度差不超过1，降低了树高，减少了磁盘的读取次数，节省了查找时间。
当数据量过大，即使红黑树，树高也不可控 ，由于数据库查找索引，每遍历一个节点，都要进行一次磁盘IO读取数据，由于磁盘IO读取数据比较慢，显得查找效率依然不是特别高。
有没有什么办法能够大大降低树高，而且可控，这样就提高了查找效率，查找索引的时间就稳定于是引出了B树，相当于二叉树的横向扩展，一个子节点存储多个索引，数据库在查找索引的时候，把这个节点的索引全部加载到内存中，然后在查找比较，这样效率就提高了很多。
B树：
然而mysql底层用的是B树的一个变种叫B+树；
- 非叶子节点不能存储data，只能存储索引，这样一个节点就可以存放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高了区间访问的性能
MYISAM存储引擎索引的实现
MyISAM的索引文件和数据文件是分离的（非聚集）
使用show global variables like "%datadir%"；查看数据库数据存放位置
在MyIsam中，数据文件有两种，MYD文件存储的是数据，MYI文件存储的索引，使用MyIsam数据库引擎进行查找时，会先去MYI去查找索引，找到后采取MYD获取数据。
InnoDB索引实现
InnoDB叶子节点的索引和行数据存放在一起（聚集表），都放在ibd文件中
一般情况下，为什么Innodb的效率更高，因为根据索引查找数据时，MyIsam需要查找两个文件，而Innodb只需要到1个文件中查找就行了，少了一次磁盘IO操作。