2.1 Buffer Implemented B Tree - KeonYeong/LKY GitHub Wiki

Overview :

On the disk-based B+ Tree, Now buffer manager is added in order to upgrade the performance of any operation. Originally, every I/O operations were executed roughly whenever I/O needed. However with the buffers available now, any I/O Requests are made to buffer manager, and the buffer manager executes minimum number of I/O operation and manages the pages requested on buffer.

Data Structure:

In buffer implementation, there are two new data structures made which each symbolize the buffer table, and the file table.

  • Buffer Table :: Buffer

    This is structure that is created in order to represent the buffer. Besides there are also some variables or control bits to represent certain status of the frame(or page) etc. Buffer

    • frame : Containing the real data of the page taken from disk.
    • table_id : The unique ID that distinguish different tables(or files) on file table.
    • pageOff : Containing the offset of the page called inside certain table(or file).
    • is_dirty : Justify whether the page on the buffer is different (written after) from the original page in the disk.
    • pin_count : The count that informs how many threads or any clients are using this page now. pin_count is increased when the appointFrame() function called, and decreased when the terminateFrame() function called.
    • LRU : In here, it is equal to 'Reference Bit' in clock algorithm. Default is 0.

  • File Table :: Table

    This is structure that represents a certain file opened. Every time the open_table() function is called, new file is opened and some variables or control bits are added to this structure in order to notice any kind of information of certain file. Table

    • ifd : It contains the input file descriptor of the certain file
    • ofd : It contains the output file descriptor of the certain file
    • name : It has the name of the file
    • inUse : This variable tells you whether current entity is already being using or not.
    • header : Contains the header page of the certain file.

Functionality:

  • Basic Functions

    • init_db : This is the function that initialize the B + tree itself. In this function the data structures - buffer pool, and the file table - are initialized and allocated.
    • open_table : With the path name as parameter, the file is opened with the open system call. In this function, file descriptors for input and output operations are created and saved on memory for future use. Moreover file is given an unique table_id and certain space in file table structure so that the program can manage multiple files. Also file headers are saved onto the file table as a member.
    • find : With the key as parameter, the program navigates through the b+ tree and find the desired key. During navigating page requests are made and any pages requested are added to the buffer pool so that it can help in the future if same page is requested. Ultimately, the value saved in the key is returned.
    • insert : First with the key given by parameter, the program tries to find whether there is already same key in the b+ tree structure, and if there is it returns fail. If not, the insertion finally begins, first the program searches which leaf node the key needs to be inserted. After then it inserts the key on the appropriate position. If the order exceeds the leaf order (in here 32) the node needs to be split into two nodes. After split the key on the middle is sent to the parent node and inserted or modified into parent node. If needed, split happens again, again and again until root.
    • delete : Like insertion, the program first searches for the key if it exists or not. If it exists, the key is deleted from the node and according to number of keys comparing to order of node, node is merged or redistributed with the neighbor(or sibling) node. Similar to insertion, processes can be repeated again until root.
    • close_table : The file is closed after the close_table method is called. All the variables of file table is initialized and it became empty. Also file header is now flushed into disk.
    • shutdown_db : All files in file tables are now erased from file table. Besides file headers are all flushed into disk.

  • Buffer Function

    • bufferRead : Reads the page requested from buffer pool. It finds the relevant page according to the table_id, and the offset. Search method is just linear search and if found the it returns the index of that page in the buffTable[]. If not, buffer manager now using the input file descriptor reads the page from the disk and saved to buffer. If buffer is full, evict one page following the some policy and put the new page on there. After saving, it set some variables or control bits explaining the page(or frame)
    • bufferWrite : It's almost same as the bufferRead() method. However when setting the control bits or variables, bufferWrite method checks one more variable which is is_dirty. After writing on the page on buffer. It turns the is_dirty flag on to indicate the page is written.
    • selectVictim : When evicting one page from the buffer, appropriate policy is used to optimize. In here selectVictim() method chooses clock algorithm in evicting the page. First iterate the buffTable, and checks the pin_count is 0 or not, if it's not 0 then pass to next page. If there's a page with 0 pin_count, it then checks the LRU which is 'reference bit' here. If it's 0 then it turns the LRU to 1 and pass again. If not 0, then finally evict that page. However if the is_dirty is 1, we first write the page on the disk and evict.

Special:

  • File Header

    File Header is also contained in buffer, but it's always on the buffer and treated as special case. It's written down to the disk only if the shutdown_db is called or close_table on the certain file(or table) is called.

  • pin_count

    pin_count is actually to indicate how many threads are using now. Hence in this implementation two methods are added in order to indicate that "I'm gonna use this page from now" and "I finished using this page". By appointFrame(index) we tell buffer manager that the page is being using and pin_count need to increment. If terminateFrame(index) is called we tell buffer manager that we have done with the page and pin_count need to decrement.

Performance:

  • Different Buffer Size graph

    This is the case of 32768 keys with the buffer size of 10 ~ 1000 sparsely.

    • It seems there're almost no change in the performance with different buffer size, but as the number of buffers increased, performance seemed to be increased also but not trivial. It's because the overhead happened with the buffer is also increased. (My guess, because of the linear search, clock algorithm etc will take much time)

return