按照官方的定义，索引就是按用户任意指定的字段对数据进行排序的一种数据结构。
索引的数据结构
假如现在有一个2列7行的表，如下图：
上图左边的：
0x07、0x56这些表示的是数据在磁盘上存储的首地址指针。
按照不同的数据结构生成的索引也是不同的，比如：
下面是以 COL2 字段建的索引：
二叉树的特点就是： 它右边的子元素是大于等于它的父元素，而左边的子元素是小于它的父元素的。
缺点：如果是插入了有小到大一次递增的索引是，数据结构就变成了链表了。结果就是建了索引跟没建一样，走的就是全表扫描。
红黑树的本质是一个二叉平衡树，当树一边链表太长的时候，它会自动平衡。
缺点： 树的高度太高，查找的次数多。
Hash表
hash算法算出字段的hash值，然后把hash值跟磁盘数据列地址指针做高速映射。
hash在等值查找的时候，性能是非常不错，但是在范围查找的时候效率就不行了。因为还是得挨个遍历出来。
B Tree
缺点：没有双向指针，范围查找的时候不如b+树。而且，b树的叶子节点存储了data，这样整个树在高度h<=3时存储的索引少了很多。
现在来看一下B+树，可以存放多少索引元素：
mysql中存储数据的单位是页，跟操作系统类似，只不过操作系统中的大小为4kb，而mysql的页的大小是16kb。
假设图中的索引是一个bigint类型的主键索引，bigint类型占8位，也就是说一个索引数据是8b，而图中的空白元素实际上是指下一个子节点的磁盘文件地址，默认占6b。这样计算一下： 16kb/(8+6) = 1170。也就是说一个页大概可存储1170个索引。这是树第一层非叶子节点，可以存这么多。第二层也是非叶子节点，同理可算： 1170 x 1170 = 1368900。可以存储1368900个索引。第三层则是页子节点，它没有下一层，但是每一个索引下面会有一个data，这个data有可能是索引所在行的磁盘文件地址，有可能是索引所在行的其他列的数据。这个不同的存储引擎，放的东西是不一样的。现在假设这个data里放的是索引所在行的其他字段信息，这样它占的空间比较大，所以假设索引+data为1kb的大小，这样，每个页就有16个索引，所以总共可以放：1170x 1170 x 16 = 21902400 个索引。 这个数量级完全够我们用的，所以mysql采用B+树这种数据结构来存储索引。
B+树的根节点是放在内存的，索引在sql查询的时候，如果树的高度h=3，最多也只会进行2次磁盘IO。
MYISAM索引文件和数据文件是分离的。（非聚集）
查看mysql文件存储位置：
show global variables like "%datadir%";
MYISAM存储引擎，在磁盘上对应有3个文件： xx.frm、xx.MYD、xx.MYI 文件，没有截图就不放了。
下面看看对应的逻辑图：
假设Col1是索引字段，那么图中，上部分B+树结构数据就是放在 xx.MYI 文件里，而下面的表一条一条数据就是放在 xx.MYD 文件中的。
InnoDB索引文件和数据是在一起的，存在于一个文件中。（聚集）
聚集索引一般都要比非聚集索引查询效率要高，因为聚集索引（聚簇索引）只需要查一个文件而非聚集索引（稀疏索引）要查2个文件（.MYI和.MYD）
多个字段组成联合索引。联合索引的底层存储结构是什么样的？
上图是由3个字段组成的联合索引。而且，不管是单值索引还是联合索引，它的叶子节点都是从左到右递增排好序的。所以它的顺序是按照（a，b，c）字段的先后顺序排的。
如果索引是由多个字段组成的联合索引，要遵循最左前缀原则。也就是：查询要从索引的最左前列开始并且不跳过索引中的列。
原文：https://www.cnblogs.com/zhaoxxnbsp/p/12699313.html