List:InnoDB Storage Engine« Previous MessageNext Message »
From:Lixun Peng Date:February 21 2013 4:25am
Subject:Re: a doubt about page directory
View as plain text  
Hi Bohu,

I think your understanding about Page Directory is wrong.

In one page, the records usually are ordered in physical, Page Directory
records some rows' offset.
So if you have these rows in a page:
[Infimum, offset:99]->[Supremum, offset:112]->[Key:0, offset 125]->...two
rows...->[Key:3, offset: 221]->...three rows..->[Key:7, offset: 349]
Then you maybe see these offsets in Page Directory:
[99, 221, 349, 112]

Why InnoDB need to use the page directory for speed up searching one row in
a page?
I think it can save parsing time, if no page directory, InnoDB need to
parse entire page, and parse each rows one by one, and then you can find
the row you need.
But if has page directory, we can use these offsets to skip some rows, for
example. we need to search Key=7, so we can go to offset 99, it's not Key
7, and then we go to offset 221, it's not Key 7, too.
Next, we go to 349, it's Key 7, it's the row I need.

That's the page directory used for.


On Thu, Feb 21, 2013 at 11:42 AM, Bohu TANG <overred.shuttler@stripped>wrote:

> Hello,
> I know the directory page is designed to faster read using binary search,
> since the records of one page is unordered(in physical).
> With the purpose of binary search, we also can do it in the same page:
> 1) When you do first search in a page, we overwrite the page with the
> ordered list(because one page is 16KB or others, but it’s very small, and
> close to the disk transfer block in modern)
> 2) The second time you search it you can do binary search internal  this
> page, so do not need the page directory.
> Why not it?
> Thanks
> ---
> BohuTANG
> "The great artist is the simplifier."--- *Vincent Van Gogh*

Senior MySQL Developer @

Mobile Phone: +86 18658156856 (Hangzhou)
Gtalk: penglixun(at)

a doubt about page directoryBohu TANG21 Feb
  • Re: a doubt about page directoryLixun Peng21 Feb
    • Re: a doubt about page directoryPaul Wilson21 Feb