就让我
她不在这里,她无处追寻,可她在我心里 -- 挥之不去
InnoDB存储引擎索引之 B+树索引

目前InnoDB 存储引擎的使用广泛,这里深入解析索引,通过了解索引内部原理来指导我们使用索引。B+树索引最常见也是 DB 中使用最频繁的一种,暂不讨论 InnoDB 的全文索引和哈希索引。不作特殊说明InnoDB指InnoDB存储引擎。


       注意B+树索引并不能找到给定键值的指定行,而是指向行所在页,然后通过 DB 把页读入内存后,在从内存中查到行数据。

DB 中B+树具有高扇出性(需要了解B+树用到的数据结构和算法即:二分查找法,二叉查找树和平衡二叉树等),所以 DB 中B+树高度一般在2~4层,即查找一行数据最多需要2~4次IO,按机械盘100次/s IO的性能,查询一次只需0.02~0.04s(SSD 就更好了)

B+树可以分为聚集索引(clustered index)和二级索引(secondary index,又称辅助索引)。

 

聚集索引

       InnoDB 表是索引组织表,即表中数据按照主键顺序存放,属于聚集索引,按照每张表的主键构造一棵B+树,叶子节点为数据页,数据页通过双向链表进行链接(聚集索引的存储并不是物理上连续的,而是逻辑上连续)。数据页只能按照一棵B+树排序,因此每张表只能有一个聚集索引(查询优化器当前倾向采用聚集索引)。

 

二级索引

通过上面介绍可知,一个表中的所有索引除了聚集索引,其他的都是二级索引(secondary index),其叶子节点并不包含行记录的全部数据,叶子结点除了包含键值以外,每个叶子结点中的索引行还包含了一个书签,该书签用来告诉存储引擎可以在哪找到相应的数据行,由于innodb引擎表是索引组织表,因此innodb存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

我们现在了解了InnoDB 存储引擎中B+树索引原理包括两种索引,以及索引对应存储的内容,接下来我们聊一下索引的使用。 

Cardinality值

并不是在所有的查询条件中出现的列都需要添加索引。什么是有添加呢,根据经验,在访问表中很少一部分数据时使用B+树索引才有意义。比如用户数据中,对于性别,地区,类型字段,即低选择性,他们取值范围小。如:

SELECT * FROM user WHERE sex =‘M

按照性别查询,只有 M,F。假设男女比例1:1,上述 SQL 语句将覆盖50%的数据,这时添加B+树索引就完全没必要了。同理可证,相反某字段选择范围广,几乎没有重复,即高选择性,使用B+树索引最合适,例如根据用户名查询,应用中基本上用户名不允许重复的。

       界定是否具有高选择性的?这个时候Cardinality值来了,可以通过SHOW INDEX 结果中的列 Cardinality 观察,如:

SHOW INDEX FROM user

图片 1.png

此值表示索引中不重复记录数量的预估值(不是准确值),Cardinality/n_rows_in_talbe 应尽可能的接近1.如果非常小,那么用户需要考虑是否有必要创建这个索引.

 

联合索引

联合索引是对表中的多列进行索引。创建方法和单个索引一样,不同之处在于使用多个索引列,如创建一张表 order.

CREATE TABLE order(
  userid INT UNSIGNED NOT NULL,
  buy_date DATE,
  KEY idx_userid (userid),
  KEY idx_userid2 (userid, buy_date)
)ENGINE=INNODB; 

上面可以看出,索引 idx_userid2为联合索引,联合的列为(userid,buy_date),那么什么情况下会使用到这个索引呢:

SELECT * FROM order where userid=1 ORDER BY buy_date desc LIMIT 3

以上优化器会使用idx_userid2 而非 idx_userid,因为在idx_userid2这个联合索引中 buy_date 已经排好序了。联合索引是“最左前缀”的,建立了联合索引相当于建立了多个索引,如联合索引(a,b,c),相当于是建立了 (a)、(a,b)、(a, b, c)三个索引,

SELECT * FROM table WHERE a=1;
SELECT * FROM table WHERE a=1 AND b=2;
SELECT * FROM table WHERE a=1 AND b=2AND c=3;

以上 sql 均可受益于联合索引(a,b,c)。

 

覆盖索引

covering index 或称索引覆盖,即从辅助索引中就可以得到查询的记录,从而不需要再查询聚集索引中的记录。前面讨论了辅助索引不包含整行记录所有信息,大小将远小于聚集索引,因此可减少大量 IO 操作。

SELECT COUNT(*) FROM order;

这里有有个误区,很多同学以为 InnoDB 会选择查询聚集索引来进行统计。其实不然,order 表中还有idx_userid2这个辅助索引,二辅助索引远小于聚集索引,所以优化器,会选择辅助索引可减少 IO 操作。

 

扇入和扇出的概念

这里通过在软件设计中的概念来解释较易理解,扇入和扇出的指应用程序模块之间的层次调用情况。

按照结构化设计方法,一个应用程序是由多个功能相对独立的模块所组成。

扇入:是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程度高。

扇出:是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高,需要控制和协调过多的下级模块;但扇出过小(例如总是1)也不好。扇出过大一般是因为缺乏中间层次,应该适当增加中间层次的模块。扇出太小时可以把下级模块进一步分解成若干个子功能模块,或者合并到它的上级模块中去。


参考书目:

MySQL技术内幕:InnoDB存储引擎(第2版)    机械工业出版社

<< 上一篇 redis cluster 搭建 What are the differences between Apache Kafka and RabbitMQ? 下一篇 >>
文章标签
随意 | Created At 2014 By William Clinton | 蜀ICP备14002619号-4 |