这篇文章是基于2014年2月3日的innodb_ruby 0.8.8版本。 在《学习InnoDB:核心之旅》中,我介绍了innodb_diagrams项目来记录InnoDB的内部,它提供了这篇文章中用到的图表。稍后,在对innodb_ruby的快速介绍中,我介绍了innodb_space命令行工具的安装和一些快速演示。 InnoDB索引页的物理结构在《InnoDB索引页的物理结构》一文中进行了描述,逻辑结构在《InnoDB的B+树索引结构》中进行了描述,行记录的物理结构在《InnoDB的行记录的物理结构》一文中进行了描述。现在我们将详细对“page directory”结构进行探讨,这个结构在之前已经出现过几次了,但还没有详细说明。 在这篇文章中,只考虑了紧凑行格式(用于Barracuda 表格式)。
如前面文章中所说明的那样,索引页中的所有记录都以一个单链接链表的形式并按升序链接在一起。但是,逐个遍历可能会包含数百条记录的页面,这样的开销非常大:必须对每个记录的key进行比较,并且必须在B+树的每个级别进行比较,直到在一个叶子页面上找到所查找的记录为止。 页目录提供一了个固定宽度的数据结构来优化这种搜索,该数据结构的直接指针按顺序指向每4-8条记录中的1条。因此,它可以用于对每个页面中的记录进行传统的二分查找,从目录的中点开始,逐步将目录遍历一半,直到只剩下一个条目,然后从那里进行线性扫描。由于该目录实际上是一个数组,因此可以按升序或降序对其进行遍历,尽管只按升序链接记录。
在《InnoDB索引页面的物理结构》中,简要介绍了页面目录的物理结构:
结构其实很简单。槽位的数量(页目录长度)在页的索引头的第一个字段中指定。页面目录总是包含一个用于infimum和supremum系统记录的条目(因此最小大小是2个条目),并且可能包含0个或更多的其他条目,每个4-8个系统记录一个条目。如果一条记录在页面目录中表示另一条记录,那么它就被称为“拥有”另一条记录。页面目录中的每个条目“拥有”目录中前一个条目之间的记录,直到并包括其本身。每个记录“拥有”的记录计数存储在每个记录之前的记录头中。 innodb_space的page-directory-summary模式可以用来查看页面目录内容,在这种情况下,对于一个完全空的表(与《innodb_ruby快速介绍》中使用的100万行的表模式相同),可以显示可能的最小页面目录:
$ innodb_space -f t_page_directory.ibd -p 3 page-directory-summary
slot offset type owned key
0 99 infimum 1
1 112 supremum 1
如果我们插入一条记录,我们可以看到,它被在页面目录中有一个条目的、key大于其本身的记录所拥有。在本例中,supremum将拥有该记录(如前所述,supremum表示高于页面中任何可能key的记录):
$ innodb_space -f t_page_directory.ibd -p 3 page-directory-summary
slot offset type owned key
0 99 infimum 1
1 112 supremum 2
临界记录总是只拥有它自己,因为没有记录可以有一个较低的key。最高记录总是拥有自己,但没有最低记录所有权。页面目录中的每个附加条目应该至少拥有4条记录(本身加上3条其他记录)和最多8条记录(本身加上7条其他记录)。 举例来说,在页面目录(粗体)中有一个条目的每条记录在单链接列表中拥有它前面的记录(K = Key, O =拥有记录的数量):
一旦任何页目录槽超过拥有的8条记录,就会重新平衡页目录以将记录分发到4条记录组中。如果我们在表中插入6条额外的记录,则supremum现在总共拥有8条记录:
$ innodb_space -f t_page_directory.ibd -p 3 page-directory-summary
slot offset type owned key
0 99 infimum 1
1 112 supremum 8
下一个插入操作将导致重组:
$ innodb_space -f t_page_directory.ibd -p 3 page-directory-summary
slot offset type owned key
0 99 infimum 1
1 191 conventional 4
2 112 supremum 5
使用带有innodb_space的记录描述器可以让你看到指向目录中每个条目的记录键,我将在以后的所有例子中使用这个描述器:
$ innodb_space -f t_page_directory.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 3 page-directory-summary
slot offset type owned key
0 99 infimum 1
1 191 conventional 4 (i=4)
2 112 supremum 5
如果一个页面完全满了,页面目录可能看起来像这样(现在使用的是100万行表本身):
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 4 page-directory-summary
slot offset type owned key
0 99 infimum 1
1 7297 conventional 5 (i=5)
2 5999 conventional 4 (i=9)
3 1841 conventional 5 (i=14)
4 14623 conventional 8 (i=22)
5 3029 conventional 4 (i=26)
<many lines omitted>
73 851 conventional 7 (i=420)
74 3183 conventional 6 (i=426)
75 1577 conventional 5 (i=431)
76 5405 conventional 5 (i=436)
77 455 conventional 5 (i=441)
78 112 supremum 6
在逻辑级别上,包含24条记录(键值从0到23)的页面目录(和记录)如下所示:
注意:
如果没有page目录,就需要比较大量的记录,以便找到正在查找的记录。演示实际代码可能是证明带有页目录的B+树的效率的最好方法。使用innodb_ruby,可以检索一个真正的InnoDB索引,尽管它还没有一个很好的命令行界面。相反,可以使用交互式的Ruby shell irb。(注意,innodb_ruby中的这个功能只是为了说明和学习的目的。它不应该被用作其他用途。) 交互式shell可以设置类似于之前innodb_space命令的配置:
$ irb -r rubygems -r innodb
irb> require "./simple_t_describer.rb"
irb> space = Innodb::Space.new("t.ibd")
irb> space.record_describer = SimpleTDescriber.new
irb> index = space.index(3)
因为我们感兴趣的主要是在这里探索,调试输出应该启用,以便各种索引遍历操作可以看到:
irb> index.debug = true
innodb_ruby库提供了两种在B+树中搜索的方法:
首先,为了调试的目的,我们将重置索引跟踪的内部统计信息(计数器):
irb> index.reset_stats
接下来,在我们的100万行表中对关键字“10000”进行线性搜索:
irb> index.linear_search([10000])
linear_search: root=3, level=2, key=(10000)
linear_search_from_cursor: page=3, level=2, start=(i=252)
linear_search_from_cursor: page=3, level=2, current=(i=252)
linear_search_from_cursor: page=36, level=1, start=(i=252)
linear_search_from_cursor: page=36, level=1, current=(i=252)
linear_search_from_cursor: page=36, level=1, current=(i=447)
<many lines omitted>
linear_search_from_cursor: page=36, level=1, current=(i=8930)
linear_search_from_cursor: page=36, level=1, current=(i=9381)
linear_search_from_cursor: page=36, level=1, current=(i=9830)
linear_search_from_cursor: page=424, level=0, start=(i=9830)
linear_search_from_cursor: page=424, level=0, current=(i=9830)
linear_search_from_cursor: page=424, level=0, current=(i=9831)
<many lines omitted>
linear_search_from_cursor: page=424, level=0, current=(i=9998)
linear_search_from_cursor: page=424, level=0, current=(i=9999)
linear_search_from_cursor: page=424, level=0, current=(i=10000)
我省略了许多行,但是完整的输出可以在linear_search.txt中看到。基本算法为:
irb> pp index.stats
{:linear_search=>1,
:linear_search_from_cursor=>3,
:linear_search_from_cursor_record_scans=>196,
:compare_key=>589,
:compare_key_field_comparison=>589}
这就比较了589条记录的键来找到我们要找的键。根本不是很有效率。
再次重置状态:
irb> index.reset_stats
这一次启动一个二进制搜索使用页目录:
irb> index.binary_search([10000])
binary_search: root=3, level=2, key=(10000)
binary_search_by_directory: page=3, level=2, dir.size=1, dir[0]=()
linear_search_from_cursor: page=3, level=2, start=(i=252)
linear_search_from_cursor: page=3, level=2, current=(i=252)
binary_search_by_directory: page=36, level=1, dir.size=166, dir[82]=(i=258175)
binary_search_by_directory: page=36, level=1, dir.size=82, dir[40]=(i=122623)
binary_search_by_directory: page=36, level=1, dir.size=40, dir[19]=(i=52742)
binary_search_by_directory: page=36, level=1, dir.size=19, dir[9]=(i=20930)
binary_search_by_directory: page=36, level=1, dir.size=9, dir[4]=(i=8930)
binary_search_by_directory: page=36, level=1, dir.size=5, dir[2]=(i=12759)
binary_search_by_directory: page=36, level=1, dir.size=2, dir[0]=(i=8930)
linear_search_from_cursor: page=36, level=1, start=(i=8930)
linear_search_from_cursor: page=36, level=1, current=(i=8930)
linear_search_from_cursor: page=36, level=1, current=(i=9381)
linear_search_from_cursor: page=36, level=1, current=(i=9830)
binary_search_by_directory: page=424, level=0, dir.size=81, dir[40]=(i=10059)
binary_search_by_directory: page=424, level=0, dir.size=40, dir[19]=(i=9938)
binary_search_by_directory: page=424, level=0, dir.size=21, dir[10]=(i=9997)
binary_search_by_directory: page=424, level=0, dir.size=11, dir[5]=(i=10025)
binary_search_by_directory: page=424, level=0, dir.size=5, dir[2]=(i=10006)
binary_search_by_directory: page=424, level=0, dir.size=2, dir[0]=(i=9997)
linear_search_from_cursor: page=424, level=0, start=(i=9997)
linear_search_from_cursor: page=424, level=0, current=(i=9997)
linear_search_from_cursor: page=424, level=0, current=(i=9998)
linear_search_from_cursor: page=424, level=0, current=(i=9999)
linear_search_from_cursor: page=424, level=0, current=(i=10000)
这就是完整的输出。这里的算法只有细微的不同:
在上面的输出中,您可以看到目录大小重复减半(dir.size),而在典型的二分查找模式中,比较的键(dir[x])重复地接近搜索键。在二分查找中,一旦找到最近的页目录条目,您可以看到简短的线性搜索(最多遍历8条记录)。 在搜索期间收集的统计数据看起来也有很大不同:
irb> pp index.stats
{:binary_search=>1,
:binary_search_by_directory=>14,
:linear_search_from_cursor=>3,
:linear_search_from_cursor_record_scans=>8,
:compare_key=>40,
:compare_key_field_comparison=>40,
:binary_search_by_directory_recurse_left=>8,
:binary_search_by_directory_recurse_right=>3,
:binary_search_by_directory_linear_search=>2}
特别要注意的是,compare_key操作只执行了40次,而在线性搜索中执行了589次。在记录比较方面,二分查找比线性搜索效率高14倍(这将会有很大的变化;根据搜索的精确值,可能是40倍以上)。