Zacard's Notes

mysql等数据库索引为什么偏爱b+tree

背景

类似mysql等数据库偏爱用b+tree这个数据结构作为索引,这是为什么呢?要解释这个原因,必须先讲下计算机组成原理中的磁盘数据存取原理。

磁盘数据读取原理

这里指普通的机械磁盘。

先看下磁盘的结构:

如上图,磁盘由盘片构成,每个盘片有两面,又称为盘面(Surface),这些盘面覆盖有磁性材料。盘片中央有一个可以旋转的主轴(spindle),他使得盘片以固定的旋转速率旋转,通常是5400转每分钟(Revolution Per Minute,RPM)或者是7200RPM。磁盘包含多个这样的盘片并封装在一个密封的容器内。上图左,展示了一个典型的磁盘表面结构。每个表面是由一组称为磁道(track)的同心圆组成的,每个磁道被划分为了一组扇区(sector).每个扇区包含相等数量的数据位,通常是512子节。扇区之间由一些间隔(gap)隔开,不存储数据。

磁盘的读写操作:

如上图,磁盘用读/写头(磁头)来读写存储在磁性表面的位,而读写头连接到一个传动臂的一端。通过沿着半径轴前后移动传动臂,驱动器可以将读写头定位到任何磁道上,这称之为寻道操作。一旦定位到磁道后,盘片转动,磁道上的每个位经过磁头时,读写磁头就可以感知到位的值,也可以修改值。对磁盘的访问时间分为寻道时间,旋转时间,以及传送时间

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,因此为了提高效率,要尽量减少磁盘I/O,减少读写操作。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页的大小通常为4KB),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

磁盘读取原理总结

一次磁盘I/O:读n页(因为存在预读),1页包含m个扇区。

先实际看下linux系统(centos)的一个扇区大小和一个页(逻辑块,一次I/O的大小)大小:

1
2
3
4
5
>fdisk -l
>磁盘 /dev/sda:500.1 GB, 500107862016 字节,976773168 个扇区
Units = 扇区 of 1 * 512 = 512 bytes
扇区大小(逻辑/物理):512 字节 / 4096 字节
I/O 大小(最小/最佳):4096 字节 / 4096 字节

可以看到一个扇区大小是512B,一个页大小为4096B,也就是一个页包含8个扇区

再看看预读的扇区数量:

1
2
>/sbin/blockdev --getra /dev/sda
>256

这里指的的是最大预读256个扇区,也就是32页。但是OS会有个自适应的过程,一般从4页(16KB)开始,在一定的时间窗口中倍增

为什么不用平衡二叉树

比如红黑树。

由于数据库索引其实也是很大的,不可能全部存储在内存中,索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度

所以,不使用平衡二叉树的原因如下:

  • 最大原因:深度太大(因为一个节点最多只有2个子节点),一次查询需要的I/O复杂度为O(lgN),而b+tree只需要O(log_mN),而其出度m非常大,其深度一般不会超过4
  • 平衡二叉树逻辑上很近的父子节点,物理上可能很远,无法充分发挥磁盘顺序读和预读的高效特性。

举例:

InnoDB存储引擎中页的大小为16KB,我们假设主键类型为BIGINT(占用8个字节,8B),指针类型为8个字节。也就是说一个页(B+Tree中的一个节点)中大概存储16KB/(8B+8B)=1K≈1000个键值。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿条记录,而且磁盘I/O最多3次。

同样10亿条数据,红黑树的深度为30,也就是最多需要30次磁盘I/O才能查询到数据。远高于b+tree

为什么用b+tree而不用b-tree

先来看看b-tree和b+tree结构比较图:

一颗b-tree:

一颗b+tree:

b+tree相对于b-tree的区别:

  • 有n棵子树的结点中含有n个索引key信息(而b-tree是n棵子树有n-1个)
  • b+tree的非叶子仅仅存储索引key信息,不包含其他列内容
  • b+tree所有的叶子结点中包含了全部索引key信息,及指向含有这些关键字记录的指针,且叶子结点本身按照索引key的大小自小而大的顺序链接(叶子节点有个指向下一个叶子节点的指针

所以,b+tree的优势在于:

  1. 深度更低,磁盘I/O更少。因为b+tree非叶子节点仅仅包含索引key信息,想比较b-tree,一个节点能够容纳更多的索引key信息,也就是树的出度更大,树的深度也就更小
  2. 查询效率更加稳定。由于非叶子节点并不包含其他列内容,所以任何关键字的查找必须走完从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当
  3. 范围查找、有序遍历非常方便。因为叶子节点之间有指针,遍历非常便捷。而b-tree就需要中序遍历才能做到
坚持原创技术分享,您的支持将鼓励我继续创作!

热评文章