Innodb索引原理和B+树

一、innodb存储引擎索引概述

    innodb存储引擎支持两种常见的索引:B+树索引和哈希索引。
innodb支持哈希索引是自适应的,innodb会根据表的使用情况自动生成哈希索引
B+树索引就是传统意义上的索引,是关系型数据库中最常用最有效的索引。B+树是从最早的平衡二叉树演变而来,但是B+树不是一个二叉树。B+中的B不代表二叉(Binary),而是代表平衡(Balance)

注意:B+树索引并不能找到一个键值对应的具体行。b+树索引只能查到被查找数据行所在的页,然后数据库通过把页读入内存,再在内存中查找,最后得到结果

二、理解B+树算法

    B+树是为磁盘及其他存储辅助设备而设计一种平衡查找树(不是二叉树)。B+树中,所有记录的节点按大小顺序存放在同一层的叶节点中,各叶节点用指针进行连接。
下面演示一个B+数结构,高度为2,每页可放4条记录,扇出(fan out)为5。从下图1可以看出,所有记录都在页节点中,并且为顺序存放,我们从最左边的叶节点开始遍历,可以得到所有键值的顺序排序:5、10、15、20、25、30、50、55、60、65、75、80、85、90

1

(1) B+树的插入操作 B+树的插入必须保证插入后叶节点的记录依然排序。同时要考虑插入B+树的三种情况,每种情况都可能导致不同的插入算法。如下表所示:

2

   我们实例分析B+树的插入,在图1的B+树中,我们需要插入28这个值。因为Leaf Page和Index page都没有满,我们直接将记录插入叶节点就可以了。如下图2所示:


图2 插入键值28
下面我们再插入70这个值,这时Leaf Page已经满了,但是Index Page还没有满,符合上面的第二种情况。这时插入Leaf Page的情况为 50、55、60、65、70.我们根据中间的值60拆分叶节点,可得到下图3所示(双项链表指针依然存在,没有画出) 
图3 插入键值70
最后我们再插入95,这个Leaf Page和Index Page都满了,符合上面第三种情况。需要做2次拆分,如下图4所示:

图4 插入键值95
可以看到,不管怎么变化,B+树总会保持平衡。但是为了保持平衡,对于新插入的键值可能需要做大量的拆分页操作。B+树主要用于磁盘,拆分意味着磁盘的操作,应该在可能的情况下尽量减少页的拆分。因此,B+树提供了旋转功能。旋转发生在Leaf Page已经满了,但是左右兄弟节点没有满的情况下。这时B+树并不是急着做页的拆分,而是旋转。旋转结果如图5所示,可以看到旋转操作使B+树减少了一次页的拆分操作,高度仍然为2.
                 图5 B+树的旋转操作

(2) B+树的删除操作 B+树使用填充因子来控制数的删除变化。填充因子可以设置的最小值为50%。B+树的删除操作同样保证删除后叶节点的记录依然排序。 根据填充因子的变化,B+树删除依然需要考虑三种情况,如下表所示:

根据图4的B+树,我们进行删除操作,首先删除键值为70的这条记录,该记录符合上表第一种情况,删除后如下图6所示:                  图6 删除键值70

接着我们删除键值为25的记录,这也是属于上表第一种情况,不同的是该值还是index page中的值。因此在删除Leaf Page中的25后,还需要将25的右兄弟节点28更新到Index Page中,如下图7所示(图中有两个笔误,红色为修正值):
                 图7 删除键值28
最后我们删除键值为60的记录。删除Leaf page键值为60的记录后,其填充因子小于50%。需要做合并操作。同样在删除Index page中相关记录后需要做Index Page的合并操作。

三、B+树索引介绍

B+树索引的本质是B+树在数据库中的实现。但是B+树索引有一个特点是高扇出性,因此在数据库中,B+树的高度一般在2到3层。也就是说查找某一键值的记录,最多只需要2到3次IO开销。按磁盘每秒100次IO来计算,查询时间只需0.0.2到0.03秒。

数据库中B+树索引分为聚集索引(clustered index)和非聚集索引(secondary index).这两种索引的共同点是内部都是B+树,高度都是平衡的,叶节点存放着所有数据。不同点是叶节点是否存放着一整行数据。

(1) 聚集索引
Innodb存储引擎表是索引组织表,即表中数据按主键顺序存放。而聚集索引就是按每张表的主键构造一颗B+树。并且叶节点存放整张表的行记录数据。每张表只能有一个聚集索引(一个主键)。
聚集索引的另一个好处是它对于主键的排序查找和范围的速度非常快。叶节点的数据就是我们要找的数据。

(2) 辅助索引
辅助索引(也称非聚集索引)。叶级别不包含行的全部数据,叶级别除了包含行的键值以外,每个索引行还包含了一个书签(bookmark),该书签告诉innodb存储引擎,哪里可以找到与索引对应的数据。
辅助索引的存在并不影响数据再聚集索引中的组织,因此一个表可以有多个辅助索引。当通过辅助索引查找数据时,innodb会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键。然后再通过主键索引找到一行完整的数据。

(3) B+树索引的管理
索引的创建和删除可以用两种方式。一种是alter table,另一种是create/drop index

MySQL索引注意的问题:对于MySQL索引的添加和删除操作,MySQL先是创建一张加好索引的临时表,然后把数据导入临时表,再删除原表,把临时表重命名为原表。
Innodb存储引擎从Innodb Plugin版本开始,支持一种快速创建索引的方法(只限于辅助索引,主键索引仍需要建临时表)。首先对表加S锁,在创建的过程中不需要重建表,但是由于上了S锁,在创建索引的过程中只能进行查询操作,不能更新数据。

四、B+树索引的使用

(1).什么时候使用B+索引

当查询表中很少一部分数据时,B+索引才有意义。对于性别,地区类型字段,他们取值范围很小,即低选择性。这时加B+索引是没有必要的。相反,某个字段取值范围很广,如姓名,几乎没有重复,即高选择性,则使用B+索引是比较合适的。因此。当访问高选择性字段并取出很少一部分数据时,该字段加B+索引是非常有效的。但是当取出的数据行占表中大部分数据时,数据库就不会使用B+索引了。

举例说明下,看下面这个团购订单表groupon_so的部分索引:

(2)顺序读、随机读与预读取
顺序读是指顺序的读取磁盘上的块,随机读是指访问的块是不连续的,需要磁盘的磁头不断移动。随机读的性能是远远低于顺序读的。
在数据库中,顺序读根据索引的叶节点就能顺序的读取所需的行数据,这个顺序读只是逻辑的顺序读,在磁盘上可能还是随机读。随机读是指访问辅助索引叶节点不能完全得到结果,需要根据辅助索引页节点中的主键去寻找实际数据行。对于一些取表里很大部分数据的查询,正式因为读取是随机读,而随机读的性能会远低于顺序读。所以优化器才会选择全部扫描顺序读,而不使用索引。
innodb存储引擎有两个预读取方法,随机预读取和线性预读取。随机预读取是指当一个区(共64个连续页)中有13个页在缓冲区中并被频繁访问时,innodb存储引擎会将这个区中剩余的页预读到缓冲区。线性预读取基于缓冲池中页的访问方式,而不是数量。如果一个区中有24个页被顺序访问了,则innodb会读取下一个区的所有页到缓冲区。但是innodb预读取经过测试后性能比较差,经过TPCC测试发现禁用预读取比启用预读取提高了10%的性能。在新版本innodb中,mysql禁用了随机预读取,仅保留了线性预读取,并且加入了innodb_read_ahead_threshold参数,当连续访问页超过该值时才启用预读取,默认值为56。

3)辅助索引的优化
通过前面可知,辅助索引的页节点包含主键,但是辅助索引的叶节点并不包含完整的行数据信息,因此,innodb存储引擎总是会从辅助索引的叶节点判断是否能得到数据。让我们看一个例子:

(4)联合索引
联合索引是指对表上的多个列做索引,联合索引的创建方法和之前的一样,如下:

联合索引还是一个B+树,不同的是联合索引键值的数量不是1,而是大于等于2.
下面我们讨论一个两个整形列组成的联合索引,假定两个键值的名称分别为a和b,如下图8所示,每个节点上有两个键值,(1,1),(1,2),(2,1),(2,4),(3,1),(3,2), 数据按(a,b)顺序进行排列

              图8 多个键值的B+树

因此,对于查询select * from t where a=xxx and b=xxx,显然可以使用(a,b)这个联合索引。对于单个a列查询 select * from t where a=xxx也是可以使用(a,b)这个索引。但是对于b列的查询select * from t where b=xxx是用不到这颗B+树索引。可以看到叶节点上b的值为1、2、1、4、1、2.显然不是排序的,因此b列的查询使用不到(a,b)索引。

联合索引的第二个好处,可以对第二键值进行排序。例如很多情况下我们需要查询某个用户的购物情况,并按照时间排序,取出最近3次的购买记录,这时使用联合索引可以避免多一次的排序操作。因为索引本身在叶节点中已经排序了。看下面示例:

本文出自http://www.ruzuojun.com
参考资料《MySQL技术内幕Innodb存储引擎》

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注