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
andBook 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 hasfour
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.