理解索引(上)

最近有个需求,要修改现有存储结构,涉及查询条件和查询效率的考量,看了几篇索引和HBase相关的文章,回忆了相关知识,结合项目需求,说说自己的理解和总结。

部分内容摘录了几个博友的文章,最后会给出文章链接,感谢他们的精彩分析。

会从以下几个方面介绍:

  • 为什么需要索引
  • 索引的类别
  • MySQL索引演化
  • MySQL索引优化
  • HBase介绍
  • HBase存储结构
  • HBase索引介绍
  • 业务需求及设计

准备分3篇文章介绍,这篇主要介绍前3小节,理解我们常常说的MySQL索引,第2篇重点介绍索引分析方法和常见索引优化,第3篇介绍下业务中使用的HBase。

为什么需要索引

总体来说,索引是为了提高查询速度的,当数据量比较大时,从头到尾依次检索是无法接受的。另外,存储的数据会包含多个属性来描述业务实体,属性可以连续或分开存储,分别对应到MySQL和HBase。

以MySQL为例,学生这个实体有学号、姓名、性别、所属班级等属性,一般还有个主键ID,现在有个需求:查询学号为002的学生姓名。

学生实体

数据是存储在磁盘上的,操作系统读取磁盘的最小单位是块,如果没有索引,会加载所有的数据到内存,依次进行检索,加载的总数据会很多,磁盘IO多。

如果有了索引,会以学号为key创建索引,MySQL采用B+树结构存储,一方面加载的数据只有学号和主键ID,另一方便采用了多叉平衡树,定位到指定学号会很快,根据关联的ID可以快速定位到对应行的数据,所以检索的速度会很快,因为加载的总数据很少,磁盘IO少。

可见,索引可以大大减少检索数据的范围、减少磁盘IO,使查询速度很快,因为磁盘IO是很慢的,是由它的硬件结构决定的。

下面,再详细介绍下磁盘存储结构和数据定位过程,加深对索引的理解。

硬盘存储结构

磁盘内部结构如下:

  • 很多个盘片被串在一个主轴上,主轴带着他们快速的旋转;
  • 每个盘片都有很多一圈一圈的磁道,每个磁道又分为一个一个的扇区;
  • 多个盘片上的同一位置的磁道组成了一个柱面;
  • 每个盘片上都有可以读写数据的磁头;

访问数据时,可以说:把1柱面,1磁头,1扇区的数据取出来?

磁盘会把1磁头挪到1柱面,就是对应的磁道, 这叫“寻道时间”,然后再旋转磁盘,让磁头指向1扇区,开始读取数据,这叫“旋转时间”,转速快的硬盘能更快的旋转到特定扇区,所以性能会更好。

结构比较复杂,但操作系统给封装了,提供了一个叫做逻辑块的方式,你看到磁盘就是有一个个“块”组成的,编号为1, 2, 3, ..n,把指定的块转化成柱面,磁头,扇区, 按照上面说的方法寻道,旋转,读取数据。

为了方便我们操作,操作系统又进一步抽象,抽象成了文件,由文件系统去保存和读取数据,我们只需要与文件打交道,文件使用inode结构,通过它可以轻松的找到这个文件所使用的所有磁盘块。

inode

扇区是对硬盘而言,块是对文件系统而言,块是文件存取的最小单位,一般一个块由连续的几个扇区组成。

一个表的数据块以链表的方式串联在一起,数据以行为单位一行一行的存放在磁盘的块中。

表在磁盘的存储

数据定位过程

以MySQL的B+树为例,简单说下几种常见场景下,数据的定位过程。

第一种场景:索引精确查找

1
select * from user_info where id = 23 ;

确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过 二分查找找到记录或未命中。

索引精确查找

第二种场景:索引范围查找

1
select * from user_info where id >= 18 and id < 22 ;

读取根节点至内存, 确定索引定位条件id=18, 找到满足条件第一个叶节点, 顺序扫描所有结果, 直到终止条件满足id >=22。

索引范围查找

第三种场景:全表扫描

1
select * from user_info where name = 'abc' ;

直接读取叶节点头结点, 顺序扫描, 返回符合条件记录, 到最终节点结束

全表扫描

第四中场景:二级索引查找

1
2
create table table_x(int id primary key, varchar(64) name , key sec_index(name) ) ;
select * from table_x where name = 'd' ;

通过二级索引查出对应主键,拿主键回表查主键索引得到数据, 二级索引可筛选掉大量无效记录,提高效率

二级索引查找

索引的类别

上面介绍了索引的优点和数据的定位过程,对其有了整体了解,另外,索引有不同种类和不同的实现方式,这节重点梳理下这些概念。

聚簇索引与非聚簇索引

简单来说,聚集索引是一种索引组织形式,索引的键值逻辑顺序决定了表数据行的物理存储顺序,而非聚集索引则就是普通索引了,仅仅只是对数据列创建相应的索引,不影响整个表的物理存储顺序。

聚簇索引的优点有:

  • 范围查询效率更高;
  • 特别适合有一小部分热点数据频繁读写的场景;
  • 通过主键访问数据时快速可达;

InnoDB引擎是聚集索引组织表,它的聚集索引选择规则是这样的:

  • 首先选择显式定义的主键索引做为聚集索引;
  • 如果没有,则选择第一个不允许NULL的唯一索引;
  • 还是没有的话,就采用InnoDB引擎内置的ROWID作为聚集索引;
主键索引和辅助索引

主键索引,简称主键,由一个或多个列组成,用于唯一性标识数据表中的某一条记录。

InnoDB数据表的主键设计通常遵循几个原则:

  • 采用一个没有业务用途的自增属性列作为主键;
  • 主键字段值总是不更新,只有新增或者删除两种操作;
  • 不选择会动态更新的类型,比如当前时间戳等;

辅助索引,常规所指的索引,也叫二级索引,又分为唯一索引和非唯一索引。

InnoDB引擎中,主键索引会被选中作为聚集索引,而唯一索引和普通辅助索引间除了唯一性约束外,在存储上没本质区别。

MySQL索引演化

本小节主要介绍索引是如何根据需求一步步演变最终成为B+树结构,基本思路是减少访问数据的总量,相应的减少磁盘IO。

密集索引(Dense Index )

根据减少无效数据访问的原则,我们将键的值拿过来存放到独立的块中。并且为每一个键值添加一个指针, 指向原来的数据块。

密集索引

当进行定位操作时,不再进行表扫描。而是进行索引扫描(Index Scan),依次读出所有的索引块,进行键值的匹配,这样带来的问题是需要很多空间来存储Dense索引。另外索引的定位效率也比较低,可以通过排序和查找算法来减少IO的访问。

假设一个块中能存储100行数据,10,000,000行的数据需要100,000个块的存储空间。假设键值列(+指针)占用一行数据1/10的空间。那么大约需要10,000个块来存储Dense索引。因此我们用大约1/10的额外存储空间换来了大约全表扫描10倍的定位效率。

折半块查找

需要对Dense进行索引,每个索引块内是有序的,另外,需要一个数组按顺序存储索引块地址,这样整体就有序了,数组也要存储到磁盘上,放在单独的块链中。

折半查找的时间复杂度是O(log2(N)),在上面的列子中,dense索引总共有10,000个块。假设1个块能存储2000个指针,需要5个块来存储这个数组。通过折半块查找,我们最多只需要读取5(数组块)+ 14(索引块log 2(10000))+1(数据块)=20个块。

折半块查找

从图中可以看到,相对于密集索引,编号是有序的。

稀疏索引(Sparse Index)

介绍基于块的折半查找时发现,读出每个块后只需要和第一行的键值匹配,就可以决定下一个块的位置(方向)。 因此有效数据是每个块的第一行数据,将每一个块的第一行的数据单独拿出来,和索引数组的地址放到一起。这样就可以直接在这个数组上进行折半查找了,这个数组就进化成了Sparse Index了。

稀疏索引

需要10个块来存储10000个Dense Index块的地址和首行键值,通过Sparse索引,仅需要读取10(Sparse块)+1(Dense块)+1(数据块)=12个块。

多层稀疏索引

因为Sparse Index本身是有序的,所以可以为Sparse Index再建sparse Index。通过这个方法,一层一层的建立 Sparse Indexes,直到最上层的Sparse Index只占用一个块为止。

多层稀疏索引

这个例子中,Sparse Index只有10个块,只需要再建立一个Sparse Index.通过两层Sparse Index和一层Dense Index查找时,只需读取1+1+1+1=4个块。

如果数据本身是基于某个Key来排序的,那么可以直接在数据上建立sparse索引,而不需要建立一个dense索引层(可以认为数据就是dense索引层),这就是说的聚集索引。

B+树

由于键值是有序的,因此可以进行范围查找。只需要将数据块、Dense Index块分别以双向链表的方式进行连接, 就可以实现高效的范围查找。如下图所示:

范围索引

这就是我们常说的B+ Tree,倒过来看下:

B+树

最后总结下它的特点:

  • 每次进行定位操作时,都从根开始查找;
  • 每层索引只需要读出一个块;
  • 最底层的Dense Index或数据称作叶子(leaf);
  • 每次查找都必须要搜索到叶子节点,才能定位到数据;
  • 索引的层数称作索引树的高度(height);
  • 索引的IO性能和索引树的高度密切相关,索引树越高,磁盘IO越多;
  • 进行范围查找时,效率很高;

参考文章:

  1. MYSQL-B+TREE索引原理
  2. 我是一块硬盘
  3. FAQ系列 | MySQL索引之聚集索引
  4. 由浅入深理解索引的实现

欢迎扫描下方二维码,关注我的个人微信公众号,查看更多文章 ~


情情说