B+树索引实战篇-Part1(索引的代价、扫描区间与边界条件)

前文非常详细的说明了Innodb储存引擎的B+树索引，我们必须熟悉下面这些观念。

• 每个索引都对应一棵B+树。B+树分为好多层，最下面一层是叶子节点(所有使用者纪录储存在这)，其余是内节点(所有目录项纪录储存在这)。
• Innodb储存引擎会自动为主键建立聚簇索引(如果没有显性指定主键及没有不允许储存NULL的UNIQUE值，那Innodb就会自动建立)，聚簇索引的叶子节点包含完整的使用者纪录。
• 我们可以为感兴趣的列建立二级索引，二级索引的叶子节点包含的使用者纪录由索引列和主键组成。如果想透过二级索引找到完整的使用者纪录，则需要再拿主键去聚簇索引内查询，这动作也叫回表。
• B+树每层节点都按照索引列的值小到大的顺序排序组成了双向链结串列，且每个页内的纪录(无论是使用者纪录或是目录项纪录)都按照索引列的值小到大的顺序行成单向链结串列。如果是联合索引，则页面和纪录先按照索引列中前列的值排序，如果值相同，再按照索引列後列的值排序。
• 透过索引寻找纪录时，是从B+树的根节点开始一层一层向下搜索的。由於每个页面(无论是内节点页面还是叶子节点页面)中的纪录都划分成了许多组，每组中索引列值最大的纪录(当然，规定Supermum纪录比任何使用者纪录都大)在页内的偏移量会被当作槽依次存放在页目录中，因此可以在页目录中透过二分法快速定位到索引列等於某个值的纪录。

这些观念那怕只有一丁点不熟悉，那麽今天的内容就不适合你，请蛙友们回去我前面的文章复习再来～

正文开始

索引的代价
索引是个好东西，但不能肆意创建。在更进一步介绍索引之前，要先了解它在时间及空间上所要付出的代价。
空间上的代价
每建立一个索引都要为其建立一棵B+树。树内每个节点都是一页(占16kb)，所以当有很多节点时是相当占空间的。

时间上的代价
每当有新增、删除、修改的动作，都需要修改索引。为了让索引符合每层节点都按照小到大排序及节点内的纪录一样按照小到大排序，都需要引擎付出额外的时间进行页分裂、页回收等操作。

为了方便说明接下来的实际查询语法与索引的关系，先建个table

mysql> create table single_table(
    -> id int not null auto_increment,
    -> key1 varchar(10),
    -> key2 int,
    -> key3 varchar(100),
    -> key_part1 varchar(100),
    -> key_part2 varchar(100),
    -> key_part3 varchar(100),
    -> common_field varchar(100),
    -> primary key (id),
    -> key idx_key1 (key1),
    -> unique key uk_key2 (key2),
    -> key idx_key3 (key3),
    -> key idx_key_part(key_part1, key_part2, key_part3)
    -> ) engine=InnoDB charset=utf8;
Query OK, 0 rows affected, 1 warning (0.05 sec)

为id列建立的聚簇索引
为key1列建立的idx_key1二级索引
为key2列建立的uk_key2二级索引，且是唯一
为key3列建立的idx_key3二级索引
为key_part1、key_part2、key_part3列建立的idx_key_part二级索引，这也是个联合索引

然後我们建立10000笔测试资料

mysql> delimiter //
mysql> create procedure insert_test_data_to_single_table()
    -> begin
    -> declare num int;
    -> set num=1;
    -> while num <= 10000 do
    -> insert into single_table(key1,key2,key3,key_part1,key_part2,key_part3,common_field) values (concat("key1", num),num,concat("key3", num),concat("key_part1", num),concat("key_part2", num),concat("key_part3", num),concat("common_field", num));
    -> set num=num+1;
    -> end while;
    -> end
    -> //
Query OK, 0 rows affected (0.02 sec)

mysql> call insert_test_data_to_single_table();
    -> //
Query OK, 1 row affected (8.85 sec)

表内就有一万笔资料辣，我们先来看看一些重要观念

扫描区间与边界条件
我们举几个例子来看
1.

select * from single_table where id >=2 and id <=100;

这个叙述是想找寻id值在[2,100]区间中的所有聚簇索引纪录。我们把待扫描id值所在的区间称为扫描区间，把这个搜索条件称为形成这个扫描区间的边界条件。

select * from single_table where key2 in (1438, 6328) or (key2 >= 38 and key2 <= 79);

该搜索条件为key2列，我们有为key2列建立uk_key2索引。如果使用uk_key2索引执行这个查询，相当於从下面三个扫描区间中获取二级索引纪录。
[1438,1438] => 对应的边界条件为key2 in (1438)。
[6328,6328] => 对应的边界条件为key2 in (6328)。
[38,79] => 对应的边界条件为key2 >=38 and key2 <= 79。
我们把[1438,1438],[6328,6328]这样只包含一个值的扫描区间称为单点扫描区间。
把[38,79]这样包含多个值的扫描区间称为范围扫描区间。
另外由於我们的查询清单是(*)，也就是需要完整的使用者纪录，所以从上述扫描区间中每获取一笔二级索引纪录，就需要做一次回表的动作。

有的搜索条件无法生成合适的扫描区间，如下：

select * from single_table where key2 > 100 or common_field = 'abc';

在使用key2的索引uk_key2查询时，扫描区间为(100,+无限大)，由於uk_key2二级索引并不按照common_field列进行排序(照key2列排序)，而且其实索引内根本就不包含common_field列，所以common_field='abc'这个条件并无法减少所需扫描的二级索引纪录，没有任何作用，其扫描区间为(-无限大,+无限大)。
由於是or的关系，联集後的扫描区间就是(-无限大,+无限大)，也就是需要扫描uk_key2的全部二级索引纪录，大家别忘了，每一笔二级索引纪录还要去执行回表操作，这个速度比全资料表扫描还更费时。所以这样的情况不如不用uk_key2索引。

如何从复杂的搜索条件中找出扫描区间：

select * from single_table where
        (key1 > 'xyz' and key2 = 748) or
        (key1 < 'abc' and key1 > 'lmn') or
        (key1 like '%suf' and key1 > 'zzz' and (key2 < 8000 or common_field = 'abc'));

首先查看where子句中的搜索条件有那些列，以及我们为那些列建立了索引。
这个查询包含key1, key2, common_field三列，key1对应二级索引idx_key1，key2对应唯一二级索引uk_key2。

然後针对可能会用到的索引，一一分析扫描区间。
第一个先使用idx_key1来看看
在搜索条件中我们可以先把对於key1没有发挥作用的条件替换为true(该条件没有任何作用跟true并无区别)，所以可以把此搜索条件看成

select * from single_table where
        (key1 > 'xyz' and true) or
        (key1 < 'abc' and key1 > 'lmn') or
        (true and key1 > 'zzz' and (true or true));

其中key1 like '%suf'变为true，补充说明一下，like叙述只有在匹配完整的字串或匹配字串字首时才产生合适的扫描区间。举个例：对於二级索引列来说，所有字串字首为'a'的纪录肯定是相邻的(因为它会照着字串大小排列，字串比较大小会先比较第一个字母，第一个字母小就是小，第一个字母相同再去比较第二个字母，依此类推)，所以只要定位到字首为'a'的第一笔纪录，沿着单向链结往後扫描，直到字串字首不为'a'为止。因此'%suf'并没有匹配字串字首，所以没有起到任何作用。

可以简化为

select * from single_table where
        (key1 > 'xyz') or (key1 < 'abc' and key1 > 'lmn') or (key1 > 'zzz'));

除了true可以替换，也可以替换掉false条件。
由於 key1 < 'abc' and key1 > 'lmn'永远为false['a'在编码中比'l'小，所以'abc'比'lmn'小(先比对第一个字元)，因此key1比'abc'小的话就不可能比'lmn'大]
替换掉false如下

select * from single_table where
        (key1 > 'xyz') or (key1 > 'zzz'));

在编码中x比z小，所以'xyz'比'zzz'小(先比对第一个字元)，这边是or运算元，所以要取联集，只要比'xyz'还大就可以符合所有条件，搜索条件就是key1 > 'xyz'。也就是说使用idx_key1来执行查询，对应的扫描区间就是('xyz',+无限大)。

最後的结果就是把满足key1 > 'xyz'条件的所有二级索引纪录取出来，针对获取的每笔纪录用主键值去回表操作，然後得到完整的使用者纪录後，再使用其他搜索条件过滤。

第二个使用uk_key2来查询
一样把不能形成合适扫描区间的条件用true换掉

select * from single_table where
        (true and key2 = 748) or
        (true and true) or
        (true and true and (key2 < 8000 or true));

简化如下(key2 < 8000 or true)的结果肯定是true罗(符合其一即可)

select * from single_table where
        key2 = 748 or true;

也就是

select * from single_table where
        true;

因此用uk_key2当索引查询，扫描区间就是没有任何限制的(-无限大,+无限大)，也就是最慢的结果，因此不考虑。

耶～take a break