在我们的日常工作中，不可避免的会遇到sql慢的问题。比如我在之前的公司，就定期收到DBA Puge发来的Oracle AWR报告，特别提醒我最近一个阶段某个SQL的执行明显变慢，可能需要优化。通常大家对这类问题的第一反应是看sql是否不合理，比如:“避免使用in和not in，否则可能导致扫描整个表”“避免where子句中对字段进行函数操作”。另一个常见的反应是这个表是否有索引。大多数情况下，添加一个索引基本就完成了。
既然题目是“从千万级数据查询谈索引结构和数据库原理”，那我们先构造一个千万级表来直观感受一下。我们创建了一个用户表，然后插入了1000万条数据。请检查:
过了近30秒，这还是单表查询，关联查询显然会更不堪。接下来，我们只需向id添加一个索引，然后验证它:
从30s到0.02s，增长了1500倍。为什么指数一下子上去了？我们从[索引数据结构]和[Mysql原理] 开始。
首先，索引数据结构 我们来看看MySQL官方对索引的定义:有两个关键词:高效搜索和数据结构。对于数据库来说，查询是我们的主要功能，查询速度肯定是越快越好。最基本的搜索是顺序搜索。为了更高效的搜索，我们自然会想到二叉树、红黑树、哈希表、BTree等等。
1.1二叉树 这个大家都很熟悉。它有一个很重要的特点:左边节点的键值比根的键值小，右边节点的键值比根的键值大。例如，图1确实可以提高我们的搜索性能。但如果作为一个数据库的索引，显然有很大的缺陷。但是对于图2所示的增量id，索引存储后变成了单边链表，肯定是不合适的。 1.2 红黑树也称为平衡二叉树。在JDK1.8之后，HashMap也将底层链表优化成了红黑树(我们可以在后续文章中谈到Hashmap1.8之后的调整)。平衡二叉树结构使树结构更好，明显提高了搜索操作的速度。但是，缺陷也是显而易见的，插入和删除操作变得复杂，从而降低了它们的操作速度。对大量数据的支持很差。当数据量很大时，树的高度太高。如果搜索到的数据是叶节点，还是会超级慢。
1.3 BTreeB-Tree是一种平衡查找树，专为磁盘等外部存储设备设计。系统从磁盘向内存读取数据时，是以磁盘块为基本单位，同一磁盘块中的数据会一次性读入内存。Mysql存储引擎中有一个页面的概念，页面是磁盘管理的最小单位。Mysql存储引擎中每页的默认大小为16KB，查看方式为:
mysql gt显示类似“innodb_page_size”的变量；
我们也可以换成4K，8K和16K。系统中一个磁盘块的存储空空间往往没有16K，所以Mysql每次申请disk 空空间时，都会连接几个地址到磁盘块，达到16KB的页面大小。Mysql将磁盘数据读入磁盘时，会以页为基本单位。在查询数据时，如果一个页面中的每一条数据都能帮助定位数据记录的位置，将会减少磁盘I/O次数，提高查询效率。
如上图所示，B树包含键值、存储子节点的指针信息以及主键以外的数据。与普通树相比，BTree增加了水平节点的容量，从而存储更多的索引。
1.4 B+Tree 在B-Tree的基础上，Daniel开发了很多变种，其中B+Tree是最常见的，MySQL一般使用B+Tree来实现其索引结构。与B树相比，B+树做了如下改进:1 .非叶节点只存储键值信息，大大增加了存储索引的数据量。2.所有叶节点之间都有一个链指针。对于区间查询，可以直接定位数据，不需要从根节点开始。3.数据记录存储在叶节点中。根据二叉树的特点，这是一个顺序访问指针，提高了区间访问的性能。通过这样的设计，一个千万级的表最多只需要三次磁盘交互就可以找到数据。
二、Mysql部分原理讲解 在这一部分，我们选择了日常面试过程中或者使用过程中的几个常见问题，以问答的形式进行讲解。 2.1、数据库引擎MyISAM和InnoDB有什么区别 MyISAM：在Mysql8之前，默认引擎是MyISAM，其目标是快速读取。特点：1、读取非常快，如果频繁插入和更新的话，因为涉及到数据全表锁，效率并不高2、保存了数据库行数，执行count时，不需要扫描全表；3、不支持数据库事务；4、不支持行级锁和外键；5、不支持故障恢复。6、支持全文检索FullText，压缩索引。建议使用场景：1、做很多count计算的，（如果count计算后面有where还是会全表扫描）2、插入和更新较少，查询比较频繁的 InnoDB：在Mysql8里，默认存储引擎改成了InnoDB。特点1、支持事务处理、ACID事务特性2、实现了SQL标准的四种隔离级别3、支持行级锁和外键约束4、可以利用事务日志进行数据恢复5、不支持FullText类型的索引，没有保存数据库行数，计算count(*)需要全局扫描6、支持自动增加列属性auto_increment7、最后也是非常重要的一点：InnerDB是为了处理大量数据时的最大性能设计，其CPU效率可能是其他基于磁盘的关系型数据库所不能匹敌的。建议使用场景1、可靠性高或者必须要求事务处理2、表更新和查询相当的频繁，并且表锁定的机会比较大的情况下，指定InnerDB存储引擎。 2.2 表和数据等在Mysql中是如何存储的我们创建一个新的数据库mds_demo，它包含两个表:order _ info和user。
我们找到了mysql存储数据的数据目录，有一个mds_demo的文件夹。同时我们还找到了order_info和user的文件。
为什么两个表产生不同的文件？原因很简单，因为这两个表是用不同的引擎创建的。
MyISAM引擎在创建表的时候，会创建三个文件.MYD文件：存放表里的数据.MYI文件：存放索引数据.sdi文件：Serialized Dictionary Information的缩写。在Mysql5里没有sdi文件，但会有一个FRM文件，用户存放表结构信息。在MySQL8.0中重新设计了数据字典，改为sdi。MyISAM的索引和数据是分开的，并且索引是有压缩的，所以存储文件就会小很多，MyISAM应对错误码导致的数据恢复的速度很快。 InnerDB引擎在创建表的时候，只有1个文件.ibd，即存放了索引又存放了文件，参见B+Tree。所以它也被称之为聚集索引，即叶子节点包含完整的索引和数据，对应的MyISAM为非聚集索引。补充说明一下：存储引擎是针对表的，而不是针对数据库，同一个库的不同的表可以使用不同的引擎。 2.3 为什么InnoDB必须要有主键，并且推荐使用整型的自增主键？通过上面的解释，这个问题其实就很清楚了。为了满足MySQL的索引数据结构B+ tree的特点，必须有一个索引作为主键，这样可以有效提高查询效率。有的童鞋可能会说，我可以创建一个没有主键的表。这其实和甲骨文的rownum是一样的。如果不指定主键，InnoDB将从插入的数据中找到一个非重复的列作为主键索引。如果没有找到非重复列，InnoDB将在后台添加一个rowId列作为主键索引。那么我们为什么不自己创建一个主键呢？
将索引的数据类型设置为integer，这样会占用较少的磁盘空或内存空。另一方面，integer比string快，string需要先转换成ASCII码，再逐个比较。
见B+树的示意图，B+树本质上是多路径多分支树。如果主键索引不是自增的，那么后续插入的索引会导致B+树的其他节点分裂和重新平衡，从而影响数据插入的效率。如果主键是自增的，只能在尾节点添加。
最后，要特别强调的是，无论当前的性能要求如何，无论数据量有多大，UUID都绝不应该用作索引。
2.4 为什么Mysql存储引擎中默认每个页的大小为16KB？假设一行数据的大小是1K，那么一页可以存储16条数据，包括指针+数据+索引。假设一行的数据大小为1K，一页(一个叶子节点)可以存储16条数据；对于非叶节点，如果在Innodb源代码中ID为bigint类型，长度为8B，指针大小为6B，总共是14B，那么一页可以存储16K/14=1170(主键+指针)，那么一棵高度为3的B+树可以存储1170117016 = 2000万的数据。所以我们面前的1000万的数据只有0.02s。
2.5 HASH算法的使用场景哈希算法是一种哈希算法，即计算某个字段的哈希，并存储在相应的地址中。在寻找数据的时候，只需要定位一次，而不是像BTree一样经过多次IO操作从根节点找到叶节点，所以查询效率非常高。但是也有很多缺点。先说最重要的两个。1.很明显hash只支持=和IN等查询，不支持范围查询。2.哈希索引在任何时候都无法避免表扫描。
