InnoDB B+tree索引

分析InnoDB为什么使用B+tree作为索引结构。

很久以前写的关于B+tree的介绍。

MySQL作为数据库,读写性能是最关键的指标。

磁盘读写与内存读写的性能差距巨大,因此需要索引来加快数据检索的速度。

本文分别从范围查询数据加载两个方面来分析B+tree索引的选择。

数据检索

数据检索实际上就是特定数据的范围查询,也就是SQL中的WHERE条件。

如果不使用索引来加速遍历的情况下,系统对磁盘的扫描属于随机I/O,查询性能非常差。

只有有序的存储结构才可以支持范围查询(WHERE A > 5 AND A < 10)

Hash索引本身不支持范围查询,只可以通过遍历全表数据来实现,时间复杂度是O(n)。

有序队列的组合索引可以实现范围查询,但是范围查询的时间复杂度O(n)。

有序树可以实现范围查询,但查询的时间复杂度与树的高度有关。

红黑树是一种有序树,高度是O(logN),其中,N为节点数量。

Btree也是一种有序树,高度是O(log(N/M)),其中,N为节点数量,M为每个树节点包含节点数量。

对于有序树来说,Btree远高度低于红黑树(取决于M的大小),从而在遍历查询的时候效率更高。

B+tree结构的叶子节点存在顺序指针,也可以加快相邻数据的检索数据。

数据加载

背景:计算机在加载内存数据时是按照页为单位来加载的,也就是说一次至少加载一个页的数据。

不同的系统页的大小不同,MACOS上是PAGE_SIZE=4096,也就是4K,因此一次内存加载至少加载4K数据。

为了提高数据库读写性能,必须减少内存的加载次数。

BtreeB+tree的区别在于非叶子节点是否存储数据

使用Btree作为索引

  • 数据会存储在所有节点
  • 范围检索会导致范围内的所有节点数据全部加载到内存中

使用B+tree作为索引

  • 数据仅存储在叶子节点
  • 范围检索仅需要把范围内的所有叶子节点数据全部加载到内存中

如上图所示,是一种数据检索内存的加载情况,其中,黄色的数据是需要检索的数据,如果按照Btree结构需要加载3次内存,而按照B+tree结构仅需要加载2次内存。