Subject | Re[3]: [Firebird-Architect] Re: Index structures |
---|---|
Author | Daniel Rail |
Post date | 2003-06-09T20:13:29Z |
Hello Ann,
Monday, June 9, 2003, 4:23:41 PM, you wrote:
AWH> Err.... We don't load the whole index into cache as a unit and
AWH> scan it. That would be horribly inefficient. The index is not
AWH> a linear list - it's a tree.
This was one part I didn't grasp before, the index is a tree. Now, I
do more clearly.
AWH> Supposing that the database has just been opened and nothing
AWH> is in cache, this is the way an indexed lookup works. The
AWH> system reads the index root page for the table. The index root
AWH> page contains the page number of the top of the tree that represents
AWH> that index. Except for very small indexes the top of the tree
AWH> contains nodes that point down in the tree rather than pointing
AWH> directly at records.
[...snip...]
AWH> With me so far? We've decided that '1zg' is the best fit.
AWH> Beside that key is a page number. In a two level index, that
AWH> page contains all the key values between 'czg' and 'dge' -
AWH> which should include our record - if it exists. Only the
AWH> top node and the node containing the record pointer are
AWH> scanned. On average, each is only half scanned.
Thanks for your patience and thorough explanation. Now, I understand
it better.
--
Best regards,
Daniel
Monday, June 9, 2003, 4:23:41 PM, you wrote:
AWH> Err.... We don't load the whole index into cache as a unit and
AWH> scan it. That would be horribly inefficient. The index is not
AWH> a linear list - it's a tree.
This was one part I didn't grasp before, the index is a tree. Now, I
do more clearly.
AWH> Supposing that the database has just been opened and nothing
AWH> is in cache, this is the way an indexed lookup works. The
AWH> system reads the index root page for the table. The index root
AWH> page contains the page number of the top of the tree that represents
AWH> that index. Except for very small indexes the top of the tree
AWH> contains nodes that point down in the tree rather than pointing
AWH> directly at records.
[...snip...]
AWH> With me so far? We've decided that '1zg' is the best fit.
AWH> Beside that key is a page number. In a two level index, that
AWH> page contains all the key values between 'czg' and 'dge' -
AWH> which should include our record - if it exists. Only the
AWH> top node and the node containing the record pointer are
AWH> scanned. On average, each is only half scanned.
Thanks for your patience and thorough explanation. Now, I understand
it better.
--
Best regards,
Daniel