|
(本文默认以mysql的innodb表来讲解)
有序的数据才更容易查找 — 有序数组
首先举个简单的例子来说明索引提高查询效率的根本原理。比如现在有一组数[12，6，4，99，8]，假如我随便给你一个数a，希望你能帮我找出a是否在这组数当中，你会怎么找？很简单，最直接的方法就是遍历，即是将a与这组数中的每一个数进行对比。若从左往右，则从第一个数12开始，a是否等于12，若是则可得结论，若不是，则跟下一个数6进行对比。显然，这种查找方法很简单粗暴，就是说运气好的话可能立马就可以得到答案，但是运气差的话，你可能要查完所有的数才能得到答案。
所以我们希望用更快的方法来确定这个答案，这个方法就是二分法。二分法也很好理解，先让这组数变成有序的[4, 6, 8, 12,99]，然后给出一个数a，首先判断a=8?，若是则可得答案，若否，再判断a>8?，若a>8，则a的取值范围落在(8,12,99]之间，重复以上步骤就可以快速确定a是否在这组数当中。
明白了没有，我们是如何快速确定a是否在一组数当中的，那就是将这组数从无序变成有序，再进行二分判断。索引能够快速确定某条数据是否在表中，也是这个道理。实际原理就是，将表中的所有数据进行排序，如何排序呢？那还不简单，你选取哪个字段作为索引，就是以该字段的值大小来排序呗。至于非数值型的字段如何排序，自然有一套方法来进行转换（此处不做详细说明，其实我也没仔细研究这块）。
可能这样说，会给你们一种似是而非的感觉，这个道理是听出来了，但是还是不明白这里面究竟是怎么实现的，不用急，听我慢慢道来。
伪原理 — 用有序数组来解释索引
举个简单的表student用来阐述（sno：学号，sex：性别）
| sno |
sex |
| 012 |
男 |
| 006 |
女 |
| 004 |
男 |
| 099 |
女 |
| 008 |
男 |
若列sno为主键，即意味着在这个字段上创建了主键索引。那创建这个主键索引是对这个表干了什么事呢，由上面我们知道，其实就是对这个表的数据进行了排序，即变成了
| sno |
sex |
| 004 |
男 |
| 006 |
女 |
| 008 |
男 |
| 012 |
女 |
| 099 |
男 |
所以当你输入查询语句
select * from student where sno = 012
数据库就会从中间点008这条数据开始查找，显然008<012，所以目标数据只可能落在008-099之间，所以继续取这段区间的中间点012，一判断刚好这条数据就是我们要的，所以输出结果。
看到这里你应该明白索引为什么能够提高查询效率了吧，对于浅尝辄止的同学，觉得自己只需要大概知道索引为何能提高查询效率，不需要真的去了解它的底层，那到这里就可以了。不过我要明确地告诉你，虽然索引能提高查询效率的确是因为将无序的数据变成有序，再用二分法进行快速定位查找，但实际上真正被应用到数据库上的原理和机制远非我上面举的例子那么简单，老实讲，我举的这个例子表述不严谨也不专业。那我为什么要这样举例子呢？只是想用最直白易懂的话先让你对索引有个直观的认识。
那么接下来，假如你希望砸破砂锅问到底，彻底搞明白这里面的底层逻辑到底是怎样的，那大可继续往下看去，知识点会很多，但不用害怕，我相信你能看懂的。
从矛盾来思考有序数组的局限性
为什么说上面的解释是有问题的？
要知道CPU处理的数据来自也只能来自内存！
即是说上面的例子中，是先把这五条数据放入内存中，才能做二分判断。那么问题来了，实际应用中一次查询涉及的可往往不止五条数据，假如是五亿条呢，难道也一口气放进内存中，合适吗？如果是更大的数据，直到内存根本放不下呢？放不进的话那就没办法做二分判断了呀，或者说判断出来的结果根本就不准确。所以实际上并不会把所有数据都放进内存中去做判断，其实就是有序数组这种数据结构还不够强大，那就换一种更强大的数据结构呗，于是就有了B+树。
比有序数组更强大的数据结构 — B+树
上面说到当数据量太大的时候，不可能把所有数据都放进内存中进行二分判断，那就只能取其中一部分数据进去了。只取一部分数据能行吗？当然可以。
想一下，如果给你一组数[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,20]，要求你查出是否有12这个数，如果内存一次最多只能放四个数进去，该怎么做呢？
1.第一次我会取9放进内存中，与12做比较，显然，9<12
2.第二次我会取[13,18]放进内存中，与12做比较，显然，12<13
3.看到步骤1,2的结论没有，9<12<13，这样我们就从查找12是否在数组
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,20]中，变成了查找12是否在原数组的子集[10,11,12]中。该子集只有三个数，可以一口气放进内存中做判断，显然这次判断可以直接得出12在该子集中，也就是说12在数组[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,20]中。
重新看回上面的步骤，一共把哪些数放进了内存中？答案是[9,10,11,12,13,18]，你看，只取大概三分之一的数据量就求出了答案！
看到这里，起码你应该知道了吧，计算机不需要把所有的数据都放进内存中去查找就能得到答案，不过有个代价就是，从磁盘取数据放到内存中这个操作，从原本的一次，变成了三次。
我知道你有疑惑要问我。为什么第一次是取9做判断，如果这还能通过二分查找原理勉强解释，那第二次取[13,18]做判断就真的没头绪了！！为什么题干中说了内存一次可以放进四个数，而我第一次只取了1个数，第二次又只取两个数呢？？？这不是浪费资源吗？？又为什么整个过程是分成3个步骤，而不是2个或者4,5个步骤呢？
不用急，这就来为你解答。
首先，你应该已经听出来我的意思了，这些取数啊，步骤啊，并不是一次偶然的选择，而是必然的选择路径。既然是必然的选择，那就肯定有一套规则决定了它一定是这个选择。
记得高中学生物的时候印象最深的就是一句话，结构决定功能，既然索引有优化查询的功能，那它必然就有一种决定了这个功能的结构。
上面实现的减少查找数据量是一个功能，必然的选择路径其实就是遵循了某种数据结构，而这种数据结构就是B+树。
现在我们通过图形来让你更加直观地理解“选择路径就是遵循了B+树的数据结构”这句话。
上图中的红色路径就是我们前面说的三个步骤。
由四个小方格构成的一个长方形，称为节点。最上面称为根节点，最下面的全部都叫叶子节点，剩下的中间部分那些节点可以叫做索引节点。
前面说到的步骤1就是把根节点的数据文件从磁盘中读进内存，不是说我们只想用9做第一步的判断，而是内存读进根节点之后，我们发现只有一条数据9，所以我们才用9做判断。那为什么这里只有一个9，而不是其他数字呢，那是因为数据存进这个节点的时候就只存了一个9啊，至于数据是怎么存进去的，为什么只存了1条数据在根节点，这点放在后面再说。
仔细看，每一条箭头的起点都是在小方格的竖边上，两个数字之间，你可以理解为这条竖边记录着下一个节点的磁盘位置。
当cpu判断12比9大时，就会取9右边最近的这条竖边，在这里找到下一个节点的磁盘位置，然后把下一个节点的数据文件读进内存中。
把第二个节点读进内存后，同样的道理，12比13小，所以找到13左边的这条竖边，就能找到下一个节点的信息，就这样一直找下去，最后一定会找到最下面的叶子节点中去。
为什么一定会找到叶子节点中去，因为只有叶子节点中才会记录完整的数据。就算一开始你不是想找12，而是找9，虽然根节点中有9这个key，但是没有value啊，所以一定会找到key包含9的叶子节点中去，在那里才能取到完整的数据，叶子节点中才会有其他字段的信息，这也是B+区别于其他树的特点之一。
说到这里，不知道你意识到没有，其实整张innodb的表，它在磁盘中就是以这种树形态存在，你在客户端看到的那张表格，其实是虚拟的。
图中的数字，其实就是每一条数据的主键，这棵树就是主索引树。区别于主索引树的，就是二级索引树，它是什么呢？就是根据这个表中其他索引建出来的，每一个非主键索引都代表一棵二级索引树。二级索引树的叶子节点中，记录的key是该索引的值，而value则是主键。即是说，你根据非主键索引去查找数据的话，都会先从这棵二级索引树上找到主键的值，再回到主索引树上去找这个主键记录的全部信息。 | 
转播
