首先，正确的创建合适的索引，是提升数据库查询性能的基础。
索引是什么？
索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。
索引的工作机制是怎样的？
如上图中，如果现在有一条sql语句 select * from teacher where id = 101，如果没有索引的条件下，我们要找到这条记录，我们就需要就行全表扫描，匹配id = 101的数据。如果有了索引，我们就可以快速的通过索引找到101所对应的行记录在磁盘中的地址，再根据给定的地址取出对应的行数据。
MYSQL数据库为什么要使用B+TREE作为索引的数据结构？
对数据的加速检索，首先想到的就是二叉树，二叉树的查找时间复杂度可以达到O(log2(n))。下面看一下二叉树的存储结构：
二叉树搜索相当于一个二分查找。二叉查找能大大提升查询的效率，但是它有一个问题：二叉树以第一个插入的数据作为根节点，如上图中，如果只看右侧，就会发现，就是一个线性链表结构。如果我们现在的数据只包含1, 2, 3, 4，5, 6，就会出现一下情况：
如果我们要查询的数据为6则需要遍历所有的节点才能找到6，即，相当于全表扫描，就是由于存在这种问题，所以二叉查找树不适合用于作为索引的数据结构。
基于这样的推演，为了解决存在线性链表的问题，很容易就能够想到平衡本文来源gaodai#ma#com搞@@代~&码网^二叉查找树。下面看看平衡二叉树是怎样的：
平衡二叉查找树定义为：节点的子节点高度差不能超过1,如上图中的节点20，左节点高度为1，右节点高度0，差为1，所以上图没有违反定义，他就是一个平衡二叉树。保证二叉树平衡的方式为左旋，右旋等操作，至于如果左旋右旋，可以自行去搜索相关的知识。
如果上图中平衡二叉树保存的是id索引，现在要从id = 8的数据，首先要把根节点加载进内存，用8和10进行比较，发现8比10小，继续加载10的左子树。把5加载进内存，用8和5比较，同理，加载5节点的右子树。此时发现命中，现在要加载id为8的索引对应的数据。
怎么找到索引对应的数据呢？
索引保存数据的方式一般有两种，第一种为在节点的数据区保存id = 8的行数据的所有数据具体内容。另外一种方式，数据区保存的是真正保存数据的磁盘地址。
到这里，平衡二叉树解决了存在线性链表的问题，数据查询的效率好像也还可以，基本能达到O(log2(n))， 那为什么mysql不选择这样的数据结构呢，他又存在什么样的问题呢？
问题1： 搜索效率不足，一般来说，在树结构中，数据所处的深度，决定了搜索时的IO次数。如上图中搜索id = 8的数据，需要进行3次IO。当数据量到达几百万的时候，树的高度就会很恐怖。
问题2： 查询不不稳定，如果查询的数据落在根节点，只需要一次IO，如果是叶子节点或者是支节点，会需要多次IO才可以。
问题3： 节点存储的数据内容太少。没有很好利用操作系统和磁盘数据交换特性，也没有利用好磁盘IO的预读能力。因为操作系统和磁盘之间一次数据交换是已页为单位的，一页 = 4K，即每次IO操作系统会将4K数据加载进内存。但是，在二叉树每个节点的结构只保存一个关键字，一个数据区，两个子节点的引用，并不能够填满4K的内容。幸幸苦苦做了一次的IO操作，却只加载了一个关键字，在树的高度很高，恰好又搜索的关键字位于叶子节点或者支节点的时候，取一个关键字要做很多次的IO。
转载请注明原文链接：深入理解Mysql的B+Tree索引原理
