next up previous contents
Next: The insert operation Up: B-heaps Previous: Node refill strategy

Selecting the fanout

Now the situation is so that we can increase the fanout d of the external heap much more freely, because the merge to refill a node can be implemented as a d-way merge of the childrens. Efficient implementation of a d-way merge is known technology and is done using an internal heap of size d. In [6] it is suggested that the fanout d is selected as large as possible. That is O(B), where B is the amount of memory pages available for buffer space. Likewise, the node size S is selected to be O(B) pages as in section 6.4.2. The idea is that during a merge, all memory should be used for the internal merge heap, in order to get as large a fanout as possible.

It should be noted that in order for this aggressive strategy to work well, it is necessary that the paging strategy is under program control. I.e. the input/output operations must be explicitly coded. The pages that are brought into memory as merge inputs, must be forced out of memory as soon as they are empty in order to keep memory available for the merge heap and the output area. Since the merge output will be needed as input for the next iteration, it should be kept in memory.



Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999