一条Select语句的执行流程
select*fromcity1WHEREcity_id=1
可以看出，SqlServer层主要是解析咱们写的sql语句，优化执行计划，InnoDB判断是否用到索引并使用索引。那么索引是啥，优势和劣势是啥，数据结构是怎么样的。
索引是什么和索引的优势和劣势
官方介绍索引是帮助MySQL高效获取数据的数据结构。更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往是存储在磁盘上的文件中的。
我们通常所说的索引，包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等，没有特别说明，默认都是使用B+树结构组织（多路搜索树，并不一定是二叉的）的索引。
索引的优势
可以提高数据检索的效率，降低数据库的IO成本，类似于书的目录；通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗；被索引的列会自动进行排序，包括和，只是组合索引的排序要复杂一些。如果按照索引列的顺序进行排序，对应orderby语句来说，效率就会提高很多。索引的劣势
索引会占据磁盘空间索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。索引的数据结构
索引的数据结构，至少需要支持两种最常用的查询需求
等值查询：根据某个值查找数据，比如：select*fromt_1userwhereage=76;范围查询：根据某个范围区间查找数据，比如：select*fromt_userwhereage=76andage=86;所以索引数据结构的选用同时需要考虑时间和空间因素。在执行时间方面，我们希望通过索引，查询数据的时间尽可能小；在存储空间方面，我们希望索引不要消耗太多的内存空间和磁盘空间。
经常使用的数据结构有：Hash表，二叉树，平衡二叉查找树（红黑树是一个近似平衡二叉树），B树，B+树。有个网站可以通过动画看到操作过程，很nice。（本来是直接放在这的，但是检测说这个是广告就删了）有需要的评论留言。
Hash表
Hash表，Java中的HashMap，TreeMap就是Hash表结构，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。
二叉查找树
二叉树特点：每个节点最多有2个分叉，左子树和右子树数据顺序左小右大。将age列构建二叉树，检索age=76的数据，只需要三次IO就可以查询到结果：30-86-76，查询效率貌似看是提升了一倍，可以看到二叉树的检索复杂度和树高相关。
那是不是任何列使用二叉树效率都会提升呢？答案是否定的。比如，将id列构建二叉树，可以看到二叉树退化为一个单向链表，查询id=6的数据，需要全表扫描，如下图，就会比较尴尬，空间复杂度高。
平衡二叉查找树
平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。
使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是O(log2n)。查询id=6，只需要两次IO。
平衡二叉树存在的问题
时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高B树：改造二叉树
MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO操作非常耗时，所以我们优化的重点就是尽量减少磁盘IO操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。那如何降低树的高度呢？
假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8+4*2=16）。
MySQL的InnoDB存储引擎一次IO会读取的一页16K的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。
为了最大化利用一次IO空间，一个朴素的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储个索引（16k/16=），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（*=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。
这种数据结构就是B树，B树是一种多叉平衡查找树，特点：
B树的节点中存储着多个元素，每个内节点有多个分叉。节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。父节点当中的元素不会出现在子节点中。所有的叶子节点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。如图：
看看b树的查询：假如需要查询值等于15的数据。查询路径磁盘块1-磁盘块2-磁盘块7。
第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，，走左路，到磁盘寻址磁盘块2。第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，，到磁盘中寻址定位到磁盘块7。第三次磁盘IO：将磁盘块7加载到内存中，在内存中从头遍历比较，15=15，找到15，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。
当然也有缺点：
B树不支持范围查询的快速查找，如果我们想要查找15和26之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。为了改进这些缺点，有了
B+树：改造B树
在B树基础上，MySQL在B树的基础上继续改造，使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题
B树：非叶子节点和叶子节点都会存储数据。B+树：只有叶子节点才会存储数据，非叶子节点只存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。B+树的最底层叶子节点包含所有索引项。B+树查找数据，由于数据都存放在叶子节点，所以每次查找都需要检索到叶子节点，才能查询到数据。B树查找数据时，如果在内节点中查找到数据，可以立即返回，比如查找值等于17的数据，在根节点中直接就可以找到，不需要再向下查找，具备中路返回的特点。
下面瞅瞅，如何使用B+树如何查询数据。
等值查询
依旧查询值等于15的数据。查询路径磁盘块1-磁盘块2-磁盘块5。
第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，，走左路，到磁盘寻址磁盘块2。第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，10，到磁盘中寻址定位到磁盘块5。第三次磁盘IO：将磁盘块5加载到内存中，在内存中从头遍历比较，15=15，找到15，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。范围查询
假如查找15和26之间的数据。查找路径是磁盘块1-磁盘块2-磁盘块5。
首先查找值等于15的数据，将值等于15的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘IO。查找到15之后，底层的叶子节点是一个有序列表，我们从磁盘块5，键值15开始向后遍历筛选所有符合筛选条件的数据。第四次磁盘IO：根据磁盘5后继指针到磁盘中寻址定位到磁盘块6，将磁盘6加载到内存中，在内存中从头遍历比较，26，=26，将data缓存到结果集。主键具备唯一性（后面不会有=26的数据），不需再向后查找，查询终止。将结果集返回给用户。可以看到B+树可以保证等值和范围查询的快速查找，所以MySQL的索引就采用了B+树的数据结构。
先整理到这，整理InnoDB和MyISAM中是如何使用B+树构建索引的。
mysql视频教程数据库5.7从入门到精通零基础自学全套DBA在线课程淘宝￥19￥60购买