next up previous
Next: IndexFile and IndexFileScan Up: Design Overview Previous: B+ Tree Page-Level Classes

Other B+ Tree Classes

Figure 2: Layout of a BTree with one BTLeafPage
\begin{figure}
% latex2html id marker 50
\begin{center}
\begin{picture}(0,0)%
\s...
...oup
\begin{picture}(285,135)(55,640)
\end{picture}\par
\end{center}
\end{figure}

Figure 3: Layout of a BTree with more than one BTLeafPage
\begin{figure}
% latex2html id marker 66
\begin{center}
\begin{picture}(0,0)%
\s...
...oup
\begin{picture}(425,325)(50,450)
\end{picture}\par
\end{center}
\end{figure}

We will assume here that everyone understands the concept of B+ trees, and the basic algorithms, and concentrate on explaining the design of the C++ classes that you will implement.

A BTreeFile will contain a header page and a number of BTIndexPages and BTLeafPages. The header page is used to hold information about the tree as a whole, such as the page id of the root page, the type of the search key, the length of the key field(s) ( which has a fexed maximum size in this assignment), etc. When a B+ tree index is opened, you should read the header page first, and keep it pinned until the file is closed. Given the name of the B+ tree index file, how can you locate the header page? The DB class (in diskmgr package) has a method

public void add_file_entry(String fname, PageId start_page_num);
that lets you register this information when a file fname is created. There are methods for deleting and reading these `file entries' ($\langle$file name, header page$\rangle$ pairs) as well, which can be used when the file is destroyed or opened. The header page contains the page id of the root of the tree, and every other page in the tree is accessed through the root page.

Figure 2 shows what a BTreeFile with only one BTLeafPage looks like; the single leaf page is also the root. Note that there is no BTIndexPage in this case. Figure 3 shows a tree with a few BTLeafPages, and this can easily be extended to contain multiple levels of BTIndexPages as well.



Subsections
next up previous
Next: IndexFile and IndexFileScan Up: Design Overview Previous: B+ Tree Page-Level Classes
2011-11-15