MySQL中索引原理教程
首先要说的是数据库的底层用的是B+树，那么什么是B+树？B+树是可以有多个子节点的树，每一层的子节点都会用链表将其连接起来
- 首先就是二叉搜索树，左边比根节点小，右边都比根节点大的，中序遍历会得到一个升序的序列。平均查找时间复杂度是O(lgn)，近似于二分查找。但要是退化成单支树的话，效率就会降低为O(n)
- 在二叉搜索树的基础上引入了AVL树（平衡二叉树），在二叉搜索树的基础上要求任何两条之路的高度差绝对值小于1，为了达到要求，就会引入旋转，而插入/删除操作较多时，时间会浪费在这个上面。所以STL中map/set中红的是红黑树
- B树：是为磁盘和外存储存设备设计的一种平衡查找树，系统从磁盘中读数据是按磁盘块（可以存多条数据）读取的。InnoDB存储引擎中有页的概念，页是磁盘管理的最小单位。默认页的大小是16KB，而系统的一个磁盘块往往没有一页的大小。因此InnoDB申请磁盘空间都是申请连续的磁盘块来达到页的大小（16KB）。在把磁盘数据读入到磁盘是以页为基本单位。在查询时，要是一个页中的每个数据都有助于定位数据的位置，就会减少IO次数，提高查询效率。B-tree就是为了让系统提高找到数据所在的磁盘块。分为三部分：指针（存储子节点的地址信息，没有数据信息），键值（主键），数据（data，除主键外的信息）。
- 数据--》磁盘块--》页（查询时通过页来定位）
- 分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。因为AVL树只能根据一个值的大小判断向右或向左，而B-Tree没一个节点有两个数据，分了三个区域，找的更快。
- B+树：是在B-Tree上的一种优化，更适合是实现外存储索引结构，InnoDB中的就用的是B+树，从B-Tree中我们看到，每个节点存储了key（键值）外，还有data（数据），每一个页的存储空间时有限的，若data数据较大时，就会使一个页存储的key数量变小了。而若是数据量很大的话，就会使树的深度变高，增加磁盘IO查询次数，进而影响效率。而在B+tree中，所有数据记录信息都按键值的顺序存储在同一层的叶子节点上，非叶子节点只存储key值，可以加大每个页存储的key值数量，降低B+Tree的高度。
B+Tree相对于B-Tree有几点不同：
- 非叶子节点只存储键值信息。
- 所有叶子节点之间都有一个链指针。
- 数据记录都存放在叶子节点中。
通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。
查找：
InnoDB中存储引擎中的页为16k，一般主键为INT（4字节），或BIGINT（8个字节）指针为（4或8字节），16K/(8+8) = 1k=(1024)个键值，深度为3的B+Tree可以维护1024^3条信息。实际中，每个页不可能被填满，因此，一般数据库中B+Tree高度在2~4层，MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。
- 上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。
- 辅助索引叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。意思就是，辅助索引先找到对应信息的主键，再进行聚集索引