索引的本质

要想搞懂索引的本质是什么，就要先看下没有索引Msql会怎样工作？mysql数据是存储在磁盘文件中，但是磁盘的数据是随机分布的，而且数据本身写入就有先有后或删除修改，原地址在存入新的数据，所以数据在磁盘的保存不一定会落在同一个磁道上，即使在同一个磁道上也不一定就是有序的。

磁盘磁道存数据示意图

如上图所示，那么对于一条sql查询语句来说，就是要对磁盘文件进行扫描读取，一次读取就是一次IO操作，假设一张表有1000万的数据，一个select语句where col=998，那么就是要逐行逐行扫描磁盘文件直到读到该数据为止。很显然这种方式效率是极低的。那我们的目的就是要减少数据的查找次数，也就是减少IO，索引就帮我们解决这个问题。

那么索引是什么？索引就是帮助MySQL高效获取数据的排好序的数据结构。

索引本质

假设有左边这么一个表，在没有索引的情况下查询 select * from t where col2=89，那么磁盘就要逐行扫描到89，这边看要扫描6次。但是用右边这棵二叉树索引，从树顶开始只要扫描两次。这棵索引树要怎么理解排好序，二叉树数据特点是从左到右，从小到大，保证索引的有序性，怎么理解数据结构，二叉树本身就是树结构数据，每个节点是key-value格式。key是要索引的数据比如89，value是数据对应的磁盘地址值比如col2=89对应的第6行数据的地址值0x77。到这里我们对索引有了基本的认识，就像大学老师说的一样索引就像一本书的目录。那么这是一颗好的索引树吗？显然不是！

索引数据结构的选择，mysql选择了B+Tree

假设我要查select * from t where col1=6 还是查第6行数据，那么我们就要对col1建索引，如果还是用二叉树合适吗？显然是不合适的，col1的数据是逐行递增的，二叉树的特点是从左到右是从小到大的。那么这样的数据建立索引放在二叉树里面会长什么样？

二叉树索引缺点

如上图：像这样单边增长的数据，用二叉树建立索引就跟链表没啥区别，如果我们查col1=6，就是对这个“链表”遍历6次，这显然是不合适，因为索引树本身也是存在磁盘文件中的，这样就相当于在磁盘中io遍历读取6次。所以这里mysql就放弃二叉树。

那么用红黑树作为索引结构会不会好一点呢？

红黑树结构的索引

可以看出，虽然数据在单边增长，但是红黑树在数据增长到一定程度的时候，就会做自动平衡操作。红黑树是一颗平衡二叉树。那么我们查col1=6，从树顶开始就只需要三次读取即可。但是呢，当数据量上来之后，假设500万的数据，那么这样一颗平衡二叉树的树高就有可能达到20左右那么要查找一个数值的时候，也是需要遍历很多的，假设树高20，查找叶子节点的数据都得查找20次。树结构的查找次数跟树的高度是紧密相关的，很显然树越高查找的次数也越多，树越低查找的次数也越少。这也是为什么mysql不用红黑树作为索引数据结构的原因。

那什么样的数据结构既然存储几百万，几千万的数据又能保证树的高度不会太高呢，B树就能满足这一点。

B树结构的索引

B树较之红黑树为什么树高更低呢？因为B树的一个节点通常是磁盘一页大小，能存储更多的索引，如上图第一个节点或者说第一页存放15,56,77三个索引，15-56之间的数据指向下一页存放20,49数据，每一个节点存储更多个数的索引，那么树高自然就更低。B树的特点，叶节点具有相同的深度，叶节点的指针为空，所有索引元素不重复，节点中的数据索引从左到右递增排列。B树查找的时候，假设查找49，先读取第一页索引到内存中（15,56,77）和49在内存中进行比较，索引本身就有序而且还在内存中比较这是非常快的，比对出在15和56之间在读取下一页索引（20,49）到内存中和49比较很快就能查到49的数据。这样整个过程下来IO操作只有2次，其他的都是内存操作，效率就提高非常多。即使如此，mysql对自身的性能要求非常高，在B树的基础上又优化出了B+树结构作为索引的数据结构。

B+树结构的索引

B+树相较于B树做了哪些优化呢？1.非叶子节点不存储data，只存储索引(冗余)，这样同样的空间可以放更多的索引。2.叶子节点包含所有索引字段并且叶子节点用指针连接，这样提高区间访问的性能。当然B树和B+树从左到右都是依次递增的，这是索引最重要的特点排好序。

B+树的查找过程跟B树的查找过程有一点区别，因为B+树的数据是只存在叶子节点的，所以B+树最终都会查到叶子节点，比如查找20，从树顶开始先读取树顶的所有索引（15,56,77）到内存，然后用二分查找或其他算法快速定位到20在15和56之间，然后在读取下一页的所有索引（15,20,49）到内存中快速找到20，此时20是不存数据的，所以还有到下一个节点也就是叶子节点拿到数据。

那么一棵高度为3的B+树能存多少数据呢？

SHOW GLOBAL STATUS like 'Innodb_page_size’; 通过这个语句可以查看到一页的大小大概是16KB。所以读取一页数据到内存比较的时候也就16KB。假设一张表的主键ID是Long类型，也就占8Byte，加上存储指针的空白位置大概是6Byte，那么一个节点也就是一页就大概可以存储16KB/14B=1170个索引。叶子节点相对特殊点存放Data数据，假设Data数据占1KB，那么叶子节点存放的数据个数就是16KB/1KB=16个。

B+树容量

那么一个高度为3的B+树大概可以存储多少数据就可以很容易的计算出来：1170*1170*16=21900000，2千多万。也就是说2000多万的数据，在B+树里面高度才3，就算它只有叶子节点才存放数据，也就3次的磁盘IO，其他都是内存比较而已。所以千万级别的数据有走索引也不是那么可怕，不走索引才是真的可怕。

所以，mysql最终为什么选择B+树而不是B树，答案也很清新了，同样是2000万的数据量，我们计算出B+树的高度只为3，而B树呢每个节点都存放数据（数据算1KB），一个节点一页（16KB）只能存放16个数据，那2000万不就是16的N次方，这个N就是B树的高度，估算下至少树高是6。树越低当然查询的磁盘IO的次数就越少。这也是B+树设计的巧妙之处，非叶子节点只放索引不放数据，可以让16kb大小的节点存储更多的索引，使得树更低。
而且B+树可以更好的支持范围查询，比如要查询大于20的数据，可以很快的通过B+索引树定位到20所在的节点，然后可以根据其排好序的特点一直往右边拿数据，拿到下一页也可以根据指针快速定位到下一页的数据，顺藤摸瓜下去快速拿到所有大于20的数据。提高区间的访问性正是这个意思，而B树是没有这个指针的，跨页的时候又得从根节点往下找。

以上就是为什么mysql选择B+树。

聚集索引和非聚集索引

mysql中在同样以B+树作为索引结构的基础上，索引还分成聚集索引和非聚集索引，当然聚集非聚集跟索引数据结构是没有什么关系的，只是在mysql中索引结构用的是B+树。简单的讲聚集非聚集就是看索引和数据是否是分开存储的，这边通过一个例子来说明下。

测试表test

上面这张test表，col1设为主键，在mysql中就会生成col1索引这么一个B+树，如果是非聚集索引，索引和数据是分开存储的，索引的叶子节点存的data为数据的地址值。在聚集索引中，索引和数据是一起存储的，索引的叶子节点存的data为具体的数据信息。

非聚集索引示意图

假设一条sql 语句 select * from test where col1=49，它的查找流程是现在B+索引树上，很快的找到49对应的地址值0x90，但是呢还有根据这个地址值去磁盘中读到具体的数据。

以MyISAM引擎建的表，就是这种非聚集索引，它会在磁盘生成tablename.frm、tablename.MYD、tablename.MYI三个文件。frm文件就是元数据、表结构相关的信息，MYD，MY就是MyISAM简写,D就是数据文件，MYI就是索引文件。对应到上图，MYI就是图绿色部分的索引树，MYD就是蓝色部分的数据。所以，可以大声的说MyISAM引擎建的表全部都是非聚集索引。

B+树聚集索引

同样是上面的查询语句，聚集索引查找起来就更简单点，通过索引树很快的定位到49的位置就直接读到其他所有信息 如：22，Tom。因为它表数据文件本身就是按B+Tree组织的一个索引结构文件，而且叶节点包含了完整的数据记录。所以从结构来讲聚集索引明显会比非聚集索引效率更高点，前者直接拿到数据，后者还有读取数据文件。

以InnoDB为引擎创建的主键索引就是这样的聚集索引，它磁盘中只会生成两个，tablename.frm、tablename.ibd。frm跟前者一样，ibd是包含了索引和数据的文件，也印证了上图的效果。

所以为什么一般都建议InnoDB表要建一个整型自增主键呢？
为什么要有主键呢？很显然，ibd文件会去构建一颗B+树索引，而这索引数据就是来自主键。如果没有主键，mysql会去选择一个所有元素都不相等的列来构建B+树索引，如果选不到mysql会去生成一个隐藏的列类似rowid这种，这个rowid来维护整张表的B+树聚集索引。而这本可以开发人员做的工作给mysql做岂不是浪费mysql的资源和性能且对我们程序可读性也很差。也就是说innodb表是一定有一个聚集索引的，有主键，这个主键索引就是聚集索引，没有的话就是隐藏的。
为什么要用整型而不是UUID或其他呢？原因也很简单，索引是有顺序的，查找索引的过程就是比大小的过程，当然整型比大小的效率比字符串比效率高的多，字符串还要逐位转ASCII码比较。36位的UUID极端情况下就是要比较36次才能比出大小。当然还有一个原因整型存储的空间更小。
为什么要递增呢？从索引的本质出发就知道，索引是排好序的，排好序才是有用的，拿来快速定位的。如果不是自增的话，插入的时候是无序的，但是索引树得保证排好序，那它就会有可能从中间节点插入，甚至重新分裂或调整来保持平衡有序。而自增的话就只要往节点末尾添加，节点满了开一个新的节点即可。

innodb表的普通索引是非聚集索引，具体往下看。

innodb表的普通索引

还是test表，以col3创建一个普通索引或者说是二级索引，索引的结构还是一棵B+树。但是呢，它的叶子节点的data为他们对应的主键ID（聚集索引的ID，这边有主键，主键索引就是聚集索引）而不是其他所有数据。所以它的查找过程会有个回表的过程。比如查询col3=Jim，很快定位到20,拿到20去主键索引那边查询所有的其他数据。
为什么mysql的普通索引要这么设计呢？一个是节约空间，这很好理解。最主要的原因是要保持一致性。如果普通索引也像主键索引那样持有所有数据，那么插入或更新数据的时候岂不是两边都要维护，但凡一边没有成功就出问题了。

联合索引的结构

一般在工作中都不建议建太多的单个索引，一般是尽量用2~3个的联合索引来覆盖百分八十，九十的查询场景。只有理解了联合索引的结构，才能更好的去建索引和优化sql语句。

联合索引

假设这边有一个 name age position 三个字段的联合主键索引，叶子节点存的是其他数据（入职日期）它是会根据索引键的先后顺序维护到节点中。先比较name，在比较age，最后比较position。
比如：
1.HanMeimei和Jeff这两个节点，根据name就能排好序HanMeimei在Jeff前面，后面的age和position就不会在去看了，哪怕28大于22。
2.左边三个Bill节点。bill都一样在比较age从左到右从小到大排序。
3.右边的两个Lilei节点。前面两个字段都相等，就按position来排序。

所以，最左前缀原理是不是就很简单了。
1. select * from t where name='bill' and age=30；
这肯定会走索引，因为它就是从name开始比较的，在比较age。因为我们的索引树就是根据name，age，position来排好序的。下面这句就没有走索引。
2.select * from t where age=30 and position='dev'；
这个就是跳过了name，我们的索引树只有以name开头比较的，不知道age开头比较的，那么第一步就比较不上，所以直接看age肯定是无序的。
像上面age=30，去索引树看下age是无序的，就没办法快速定位到，因为有序的话定位到第一个age=30就不在查找了，后面都是不用在比较的，而现在后面还有比30小的数和等于30的数，那结果肯定是不对的。再如查找age>30，如果有序的话，后面的age都是大于30的直接读取出来，但是跳过了name，age的数据还是有序的吗？显然不是30,31,32,28,22,30,30等都是无序的，如果有序找到age=30，后面都不要看都是比30大，但是还有各种无序大小不一的数据，那对不起只能全表扫描才能找到匹配的数据。

总而言之，索引就是帮助MySQL高效获取数据的排好序的数据结构。