Implementation of Heap File in C++. It tree will have a parameters: page_size

  • Each page will have a fixed size.
  • Each page is divided into two parts: Data Area and Book Keeping Area.The data area grows from beginning of the page to the end of the page.The book keeping area grows in the reverse direction.A new blank page has four integers stored at the end of page:
    • Address of previous page
    • Address of next page
    • Count of the number of records in the page
    • Start address of free space within the page
NOTE: Assume that each integer requires 4 bytes of storage.

To store a record into the page, you need to create a directory entry in the book keeping area.This entry will store pointer to the beginning of the record in the page. Assume that this pointer is an integer value.To store a record of size R Bytes, the space occupied in the page is R+4 Bytes.


Line 1 contains the value of page_size Line 2 onwards descibes various operation to be performed  1 : Insert new value    Parameter: Record_size and Value  2 : Display The Status  3 : Search for a value    Parameter: Value  4 : Exit


For operation 2, output will be one line containing number of pages and number of records in each page separated by space and terminated by \n. For operation 3, output will be one line containing page id and slot id if the value is found and -1 -1 if the value is not found.


View Github