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?