edu.berkeley.cs186.database.index

Class BPlusTree

java.lang.Object

edu.berkeley.cs186.database.index.BPlusTree

public class BPlusTree
extends Object

A B+ tree. Allows the user to add, delete, search, and scan for keys in an index. A BPlusTree has an associated page allocator. The first page in the page allocator is a header page that serializes the search key data type, root node page, and first leaf node page. Each subsequent page is a BPlusNode, specifically either an InnerNode or LeafNode. Note that a BPlusTree can have duplicate keys that appear across multiple pages. Properties: allocator: PageAllocator for this index keySchema: DataBox for this index's search key rootPageNum: page number of the root node firstLeafPageNum: page number of the first leaf node numNodes: number of BPlusNodes

Field Summary

Fields

Modifier and Type	Field and Description
protected PageAllocator	allocator
static String	FILENAME_EXTENSION
static String	FILENAME_PREFIX
protected DataBox	keySchema

Constructor Summary

Constructors

Constructor and Description
BPlusTree(DataBox keySchema, String fName) This constructor is used for creating an empty BPlusTree.
BPlusTree(DataBox keySchema, String fName, String filePrefix)
BPlusTree(String fName) This constructor is used for loading a BPlusTree from a file.
BPlusTree(String fName, String filePrefix)

Method Summary

Methods

Modifier and Type	Method and Description
boolean	containsKey(DataBox key) Perform an equality search on the specified key.
void	decrementNumNodes()
boolean	deleteKey(DataBox key, RecordID rid) Delete an entry with the matching key and RecordID.
int	getNumNodes()
int	getNumPages() Return the number of pages.
void	incrementNumNodes()
void	insertKey(DataBox key, RecordID rid) Insert a (Key, RecordID) tuple.
Iterator<RecordID>	lookupKey(DataBox key) Perform an equality search on the specified key.
Iterator<RecordID>	sortedScan() Perform a sorted scan.
Iterator<RecordID>	sortedScanFrom(DataBox keyStart) Perform a range search beginning from a specified key.
protected void	updateRoot(int pNum) Update the root page.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

FILENAME_PREFIX

public static final String FILENAME_PREFIX

See Also:

Constant Field Values

FILENAME_EXTENSION

public static final String FILENAME_EXTENSION

See Also:

Constant Field Values

allocator

protected PageAllocator allocator

keySchema

protected DataBox keySchema

Constructor Detail

BPlusTree

public BPlusTree(DataBox keySchema,
         String fName)

This constructor is used for creating an empty BPlusTree.

Parameters:

keySchema - the schema of the index key

fName - the filename of where the index will be built

BPlusTree

public BPlusTree(DataBox keySchema,
         String fName,
         String filePrefix)

BPlusTree

public BPlusTree(String fName)

This constructor is used for loading a BPlusTree from a file.

Parameters:

fName - the filename of a preexisting BPlusTree

BPlusTree

public BPlusTree(String fName,
         String filePrefix)

Method Detail

incrementNumNodes

public void incrementNumNodes()

decrementNumNodes

public void decrementNumNodes()

getNumNodes

public int getNumNodes()

sortedScan

public Iterator<RecordID> sortedScan()

Perform a sorted scan. The iterator should return all RecordIDs, starting from the beginning to the end of the index.

Returns:

Iterator of all RecordIDs in sorted order

sortedScanFrom

public Iterator<RecordID> sortedScanFrom(DataBox keyStart)

Perform a range search beginning from a specified key. The iterator should return all RecordIDs, starting from the specified key to the end of the index.

Parameters:

keyStart - the key to start iterating from

Returns:

Iterator of RecordIDs that are equal to or greater than keyStart in sorted order

lookupKey

public Iterator<RecordID> lookupKey(DataBox key)

Perform an equality search on the specified key. The iterator should return all RecordIDs that match the specified key.

Parameters:

key - the key to match

Returns:

Iterator of RecordIDs that match the given key

insertKey

public void insertKey(DataBox key,
             RecordID rid)

Insert a (Key, RecordID) tuple.

Parameters:

key - the key to insert

rid - the RecordID of the given key

deleteKey

public boolean deleteKey(DataBox key,
                RecordID rid)

Delete an entry with the matching key and RecordID.

Parameters:

key - the key to be deleted

rid - the RecordID of the key to be deleted

containsKey

public boolean containsKey(DataBox key)

Perform an equality search on the specified key.

Parameters:

key - the key to lookup

Returns:

true if the key exists in this BPlusTree, false otherwise

getNumPages

public int getNumPages()

Return the number of pages.

Returns:

the number of pages.

updateRoot

protected void updateRoot(int pNum)

Update the root page.

Parameters:

pNum - the page number of the new root node