vlambda博客
学习文章列表

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

    MySQL中数据是索引组织表,即表中数据按照主键顺序存放。所以就可以基于索引这种数据结构实现一些高级算法,来提高检索效率。


常见的查找算法

顺序查找:复杂度O(n),在数据量大时,效率很低

二分查找:在有序为前提,复杂度O(logn)
hash查找:无法满足范围查找
二叉树查找:O(logn),每个节点只能有一个左节点和一个右节点

试着用二叉树来构造一种索引方式


为什么MySQL没有采用二叉树来构造索引呢?
由磁盘的物理结构决定的。

首先,二叉树中每个节点只能有一个左节点和一个右节点,直接导致树的高度很高,逻辑上相近的节点,无法利用局部性,相邻节点没法直接通过指针相连,可能需要返回上层节点重复递归找到结果,效率低。

其次,当数据量大时,内存不够,大部分数据只能存放在磁盘上,只有在需要的时候才加载到内存中,但是磁盘读取速度显然与内存差很多,大部分时间会阻塞在IO上面,为了减少磁盘IO次数,上面这些传统的树无法满足。

        

磁盘结构


下面是磁盘整体结构示意图

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

其中,磁盘可以转动(各个磁盘必须同步转动)。每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动)。


盘片结构示意图

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。

磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。

磁盘如何读取数据?

磁盘如何可以提高IO效率?

为了提高效率,要尽量减少磁盘I/O,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)(在许多操作系统中,页大小通常为4k)的整倍数。主存和磁盘以页为单位交换数据。

当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

为了减少磁盘 IO 次数,B-/B+树应运而生。


B-/B+树

B-

为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。

所以新建节点时,直接申请页大小的空间,计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。那么总 IO 的次数就缩减为了 log n 次。

下面是一棵简化的B-树:

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。每个 key 值紧跟着 data 域,B-树的 key 和 data 是聚合在一起的。

B-树的如何进行查找的?

比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。


B+

B+树是B-树的变种,它与B-树的不同之处在于:

  • 在B+树中,key 副本存储在内部节点,真正的 key 和 data 存储在叶子节点上 。

  • n 个 key 值的节点指针域为 n 而不是 n+1。

  • 为了增加 区间访问性,一般会对B+树做一些优化,增加了顺序访问指针。

下面是一棵简化的B+树:

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

因为增加了顺序访问指针,图中如果要查询key为从55到62的所有数据记录,当找到50后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

B-树与B+树区别

1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)

如上图,如果查找50,刚好第一次就可以查找出来,所以最好情况是O(1)。由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)

2.B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找

B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。


MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

索引分为:

  • 聚集索引(Primary key)按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据,也将聚集索引的叶子节点称为数据页。每个数据页都通过一个双向链表来进行链接。每张表只能拥有一个聚集索引

  • 辅助索引(Secondary key)叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外,还包含一个书签,该书签找到与索引相对应的行数据。每张表可以有多个辅助索引。

MyISAM引擎的实现

下图是MyISAM索引的原理图:

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

在MyISAM中,主索引和辅助索引在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

InnoDB引擎的实现

而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。

这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

下图是InnoDB主索引示意图:

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有)。

下图为定义在Col3上的一个辅助索引:

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

这里以英文字符的ASCII码作为比较准则。辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

这里就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。

非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。


数据的查找

1、精确查找: select * from user_info where id = 23

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

复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

2、索引范围查找:select * from user_info where id >= 18 and id < 22

内存中找到根节点,确定索引定位条件id=18,找到满足条件第一个叶节点

,顺序扫描所有结果,直到终止条件满足id >=22 


复习系列之数据库(四):MySQL为什么采用B+树作为索引结构?

3、全表扫描:select * from user_info where name = 'abc'

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

4、二级索引查找:Select * from table_x where name = “d”;

id是主索引,name是二级索引。

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


参考文献:1、《MySQL技术内幕》