When an ISAM index is built, how is the number of leaf nodes per index node (the "fan-out") calculated? 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?
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.