索引是帮助数据库高效获取数据的排好序的数据结构。
数据是如何存储与读取的？
1. 索引采用了什么数据结构呢？
常见的数据结构有：hash、二叉树、红黑树、B树、B+树。
首先来看如果采用Hash，它是把数据进行Hash直接对应磁盘存储引用地址，这样查找数据直接告诉磁盘数据在哪，查询很快。但是 hash 还是有些不足：那就是不能范围查找，如果通过大于或者小于去筛选数据，就需要扫描整个hash表，效率大大降低了。当然mysql还是提供了Hash索引，毕竟有些场合还是用起来也不错。
采用二叉树，每个节点存储了索引对应字段的值，这样我们根据索引去查询时就可以避免全表扫描，时间复杂度降为O(log n)。看起来很美好，但是二叉树在值单边递增的情况下回退化到链表。
采用红黑树，又叫自平衡二叉树，会通过特定操作保持二叉查找树的平衡，避免了单边增长的问题，从而获得较高的查找性能。
从上面我们发现，红黑树相比较于二叉树又进步了一些，但红黑树还是有些问题：那就是数据量大的话，红黑树的深度会很深，也就是说深度不可控，这样一来查找数据还是会很耗时。100w数据时树的高度大概在20左右，那也就是说从有着100w条数据的平衡二叉树中找一个数据，最坏的情况下需要20次磁盘的IO查找。是不是可以每个节点多增加一些数据呢?
B树的结构为：
动态演示数据结构的网站
B树的特点：
1.叶子节点具有相同的深度，叶子节点的指针为空
2.所有索引元素不可重复
3.节点中数据索引是有序的，即从左到右递增
实际上mysql使用的是B+树
B+树是在B树基础上的一种优化，使其更适合实现存储索引结构。B+树与B树的结构很像，但是也有几个自己的特性：
1、所有的非叶子节点只存储索引信息，因此可以放更多的索引
2、叶子结点中包含了全部索引信息。
3、所有叶子节点之间都有一个链指针，来提高区间访问的性能
为什么要做这样的改进呢？我们还需要了解的一个知识点是操作系统从磁盘读取数据到内存是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来。即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。
预读的长度一般为页（page）的整数倍，InnoDB预读大小默认为16K。页是计算机管理存储器的逻辑块，操作系统往往将磁盘存储区分割为连续的大小相等的块，每个存储块称为一页，在许多操作系统中页的大小通常为4k。
B+树相比B树有哪些优势呢？
1.由于B+树所有的索引都在叶子结点，并且结点之间有指针连接，在找大于某个关键字或者小于某个关键字的数据的时候，B+树只需要找到该关键字然后沿着链表遍历就可以了，而B树还需要遍历该关键字结点的根结点去搜索。
2.由于B树的每个结点（这里的结点可以理解为一个数据页）都存储索引+实际数据，而B+树非叶子结点只存储索引信息。而每个节点也就是每个页的大小是有限的，所以B树同一页能存储的数据会比B+树存储的更少。这样同样总量的数据，B树的深度会更大，增大查询时的磁盘I/O次数，进而影响查询效率。
总的来说B+树即减少了查询次数也提高了很好的范围查询性能。
2. MyISAM和InnoDB
每个表可以使用不同的存储引擎。开发中使用最多的是InnoDB存储引擎。
索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。
2.1 MyISAM的索引实现（非聚集）
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的存储地址。对应硬盘文件里每个表都有（.MYD data)数据 + (.MYI index)索引 + (.frm frame)结构三个文件。
下图是MyISAM索引的原理图：
这里设表一共有三列，假设我们以Col1为主键，则下图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一棵B+树，data域保存数据记录的地址。因此MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引（索引还会缓存进内存），如果指定的Key存在，则取出其data域中保存的存储地址，去磁盘读取相应的数据记录（称为回表）。
2.2 InnoDB的索引实现（聚集索引）
InnoDB的数据文件本身就是按B+树组织的一个索引结构文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录，这个索引的key是数据表的主键。
上图是InnoDB主索引（同时也是表数据文件）的示意图，可以看到叶子节点包含了完整的数据记录。这种索引叫做聚集索引。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值。下图为定义在Col3上的一个辅助索引：
辅助索引的data存储主键的节点不仅可以节省内存空间，而且利于保证数据的一致性，修改值只要修改主索引文件就行了。
聚集索引这种实现方式使得如果按主键的搜索不需要回表操作比MyISAM高效很多，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白：
为什么不建议使用过长的字段作为主键？
因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。为什么InnoDB必须要求有主键？
InnoDB的数据文件本身按B+树聚集，所以表必须有主键来作为唯一标识。如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键。为什么InnoDB推荐使用整型的自增主键？
首先选择整型因为比较节省存储空间。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页，不用重新排位。如果不是自增的主键，非有序增长的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，频繁的插入和删除那会导致数据页产生碎片，页的空间利用率低，还会导致树变的“虚高”，降低查询效率！
联合索引
开发中一般推荐使用联合索引，因此很多索引的建立原则都和联合索引有着重要关系
下面是联合索引的底层存储结构
