Efficiently traversing InnoDB B+Trees with the page directory--slot

因此directory最少有2个slot。一个记录假设own其它记录，表示在这个slot里。每一个slot管理本身和上一个slot中的记录之间的记录。记录owned的个数存在每一个记录的record header部分。

The page-directory-summary mode of innodb_spacecan be used to view the page directory contents, in this case for a completelyempty table (with the same schema as the 1 million row table used in A quickintroduction to innodb_ruby), showing the minimum possible page directory:

$ innodb_space -f t_page_directory.ibd -p 3page-directory-summary

slot                       offset          type       owned   key

0             99     infimum       1      

1         112     supremum      1 

If we insert a single record, we can seethat it gets owned by the record with a greater key than itself that has anentry in the page directory. In this case, supremum will own the record (aspreviously discussed, supremum represents a record higher than any possible keyin the page):

$ innodb_space -f t_page_directory.ibd -p 3page-directory-summary

slot   offset      type          owned   key

0      99      infimum          1      

1      112     supremum        2      

The infimum record always owns only itself,since no record can have a lower key. The supremum record always owns itself,but has no minimum record ownership. Each additional entry in the pagedirectory should own a minimum of 4 records (itself plus 3 others) and amaximum of 8 records (itself plus 7 others).

Infimum记录总是仅仅own自己，由于是最小记录。

Supremum记录总是own自己。

除了infimum和supremum的slot，每一个slot都会至少管理4个记录（itself+3others）。最多管理8个。

To illustrate, each record with an entry inthe page directory (bolded) owns the records immediately prior to it in thesingly-linked list (K = Key, O = Number of Records Owned):

3、Growth of the page directory

Once any page directory slot would exceed 8records owned, the page directory is rebalanced to distribute the records into4-record groups. If we insert 6 additional records into the table, supremumwill now own a total of 8 records:

一旦一个slot管理的记录超过8个，slot就会将之分成4个记录为一组。假设我们插入6个记录，supremum slot会拥有8个记录。

$ innodb_space -f t_page_directory.ibd -p 3page-directory-summary

slot   offset      type          owned   key

0      99      infimum          1      

1      112     supremum        8    

The next insert will cause are-organization:

在插入一个记录会引起重组

$ innodb_space -f t_page_directory.ibd -p 3page-directory-summary

slot   offset      type          owned   key

0      99      infimum          1      

1      191     conventional      4      

2      112     supremum        5   

4、A logical view of the page directory

At a logical level, the page directory (andrecords) for a page with 24 records (with keys from 0 to 23) would look likethis:

Infimum总是仅仅own自己，该slot的n_owned=1

Supremum总是owns一个页中最后几个记录，个数能够小于4.

其它slot至少有4个记录最多8个。

逆序排放。从16376个字节開始。即FIL trailer的開始位置。

Take note that:

Records are singly linked from infimum tosupremum through all 24 user records, as previously discussed.

Approximately each 4th record is enteredinto the page directory, represented in the illustration both by bolding thatrecord and by noting its offset in the page directory array represented at thetop of the illustration.

The page directory is stored “backwards” inthe page, so is reversed in this illustration compared to its ordering on disk.

记录是单链表形式链接

http://blog.jcole.us/2013/01/

Efficiently traversing InnoDB B+Trees with the page directory--slot

标签：spi   always   tin   text   nim   cee   try   tree   rem