2
$\begingroup$

I asked this question on DB.SE but it didn't get any traction, so I'll ask it here...

The following statement is in the Ramakrishnan text (2nd ed. page 252):

(emphasis in bold is mine)

The non-leaf pages direct a search to the correct leaf page. The number of disk I/Os is equal to the number of levels of the tree and is equal to $log_FN$, where $N$ is the number of primary leaf pages and the fan-out $F$ is the number of children per index page. This number is considerably less than the number of disk I/Os for binary search, which is $log_2N$; in fact, it is reduced further by pinning the root page in memory. The cost of access via a one-level index is $log_2(N/F)$. If we consider a file with $1,000,000$ records, $10$ records per leaf page, and $100$ entries per index page, the cost (in page I/Os) of a file scan is $100,000$, a binary search of the sorted data file is $17$, a binary search of a one-level index is $10$, and the ISAM file (assuming no overflow) is $3$.

Question: How is the value of F calculated when the index is constructed?

From the example given it seems the structure will be:

  • root node containing 1,000 pointers to index nodes
  • one level of 1,000 index nodes, each containing a pointer to 100 leaf nodes
  • 100,000 leaf nodes, each containing ten records

Assuming that is the correct understanding of what he describes, what determines the value of $F$ when the index is built? Is it calculated in such a way that the index will have exactly 3 levels and so $F$ is set to ensure we can reach all leaf nodes in 3 steps? This doesn't seem to be the case since he has a diagram elsewhere in the book of an ISAM index with more than 3 levels.

So then what dictates the value of $F$? i.e. what keeps it from being 1K or 100K?

$\endgroup$
2
$\begingroup$

In a page-structured file, each page has a fixed size. This effectively eliminates internal fragmentation.

Each index page needs to store a bunch of keys and corresponding pointers to other disk pages. The number of keys-and-pointers that can be stored in a disk page is what determines F.

So how big is a page?

In a real-world DBMS, the lower limit is the virtual memory page size, which is determined by the hardware and the operating system. The physical block size of a disk is typically smaller than this, so that's not a concern. Setting your file page size to be some multiple of the VM page size lets the operating system buffer cache act as the database buffer cache.

The upper limit is set by efficiency considerations, since pages which are too big require more I/O and also potentially wastes space when pages are under-full.

So in practice, a small power-of-two multiple of the VM page size is appropriate.

$\endgroup$
  • $\begingroup$ Thanks for the answer. So to make sure I get it: the fan-out is calculated automatically by the DBMS based on page size at the time the index is built, and that calculation is directly influenced by the page size established by the DBA, correct? If so I would assume that also applied to B+ trees as well, with the understanding that they can grow/shrink as needed, in units of a page at a time. $\endgroup$ – Dave Feb 23 '17 at 19:05
  • $\begingroup$ Yes. One of the dirty little secrets of real-world B-trees (and other index file structures) is that their fanout is often dynamic, since keys (e.g. strings) are typically not of a fixed size. $\endgroup$ – Pseudonym Feb 23 '17 at 23:40
  • $\begingroup$ Ok great -- I understand it much better now, thank you! $\endgroup$ – Dave Feb 24 '17 at 1:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.