edu.berkeley.cs186.database.index

Class BPlusNode

java.lang.Object

edu.berkeley.cs186.database.index.BPlusNode

Direct Known Subclasses:

InnerNode, LeafNode

public abstract class BPlusNode
extends Object

A B+ tree node. A node is represented as a page with a page header, entry bitmap, and entries. The type of page header and entry are determined by the subclasses InnerNode and LeafNode. Properties: keySchema: DataBox for this index's search key entrySize: physical size (in bytes) of the page entry of this node numEntries: number of entries this node can hold bitMapSize: physical size (in bytes) of a page header entry bitmap headerSize: physical size (in bytes) of the rest of the page header tree`: BPlusTree containing this node pageNum`: page number corresponding to this node

Field Summary

Fields

Modifier and Type	Field and Description
protected int	numEntries

Constructor Summary

Constructors

Constructor and Description
BPlusNode(BPlusTree tree, boolean isLeaf) Abstract constructor for BPlusNode for new nodes.
BPlusNode(BPlusTree tree, int pageNum, boolean isLeaf) Abstract constructor for BPlusNode for existing nodes.

Method Summary

Methods

Modifier and Type	Method and Description
protected List<BEntry>	getAllValidEntries() Return a list of valid, existing entries of this node.
static BPlusNode	getBPlusNode(BPlusTree tree, int pageNum) Return an existing Node from a BPlusTree and pageNum.
Page	getPage() Fetch Page this BPlusNode exists on.
int	getPageNum()
BPlusTree	getTree() Retrieve the BPlusTree that this BPlusNode belongs to.
boolean	hasSpace()
InnerEntry	insertBEntry(LeafEntry ent) Insert an entry into this node.
boolean	isLeaf()
LeafNode	locateLeaf(DataBox key, boolean findFirst) Recursively locate the child that leads to the leaf node.
protected void	overwriteBNodeEntries(List<BEntry> entries) Clear all the entries of this node, and write all the given entries into the node, starting from the first entry number.
InnerEntry	splitNode(BEntry newEntry) Split BPlusNode driven by new entries.

Methods inherited from class java.lang.Object

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

Field Detail

numEntries

protected int numEntries

Constructor Detail

BPlusNode

public BPlusNode(BPlusTree tree,
         int pageNum,
         boolean isLeaf)

Abstract constructor for BPlusNode for existing nodes.

Parameters:

tree - the BPlusTree this Node belongs to

pageNum - the pageNum where to open this node on

isLeaf - is this node a leaf

BPlusNode

public BPlusNode(BPlusTree tree,
         boolean isLeaf)

Abstract constructor for BPlusNode for new nodes. Auto-allocates a Page for this node.

Parameters:

tree - the BPlusTree this Node belongs to

isLeaf - is this node a leaf

Method Detail

getBPlusNode

public static BPlusNode getBPlusNode(BPlusTree tree,
                     int pageNum)

Return an existing Node from a BPlusTree and pageNum.

Parameters:

tree - the BPlusTree this Node belongs to

pageNum - the page number on where this node exists on

Returns:

BPlusNode object that exists on this Page

getPage

public Page getPage()

Fetch Page this BPlusNode exists on.

Returns:

the Page that this BPlusNode exists on

getPageNum

public int getPageNum()

hasSpace

public boolean hasSpace()

getTree

public BPlusTree getTree()

Retrieve the BPlusTree that this BPlusNode belongs to.

Returns:

the BPlusTree that owns this node

splitNode

public InnerEntry splitNode(BEntry newEntry)

Split BPlusNode driven by new entries.

isLeaf

public boolean isLeaf()

getAllValidEntries

protected List<BEntry> getAllValidEntries()

Return a list of valid, existing entries of this node.

Returns:

a list of entries that have the valid bit set

overwriteBNodeEntries

protected void overwriteBNodeEntries(List<BEntry> entries)

Clear all the entries of this node, and write all the given entries into the node, starting from the first entry number.

Parameters:

entries - the list of entries to write

insertBEntry

public InnerEntry insertBEntry(LeafEntry ent)

Insert an entry into this node.

Parameters:

ent - the entry to insert

locateLeaf

public LeafNode locateLeaf(DataBox key,
                  boolean findFirst)

Recursively locate the child that leads to the leaf node. If a key spans multiple pages and findFirst is true, this method returns the first leaf that contains the key. Otherwise, it returns the last leaf that contains the key.

Parameters:

key - the key to search for

findFirst - if true, returns the first leaf with the key

Returns:

the LeafNode found