org.netbeans.mdr.persistence.btreeimpl.btreeindex
Class BtreePage

java.lang.Object
  extended by org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage
All Implemented Interfaces:
Streamable
Direct Known Subclasses:
BigKeyPage, FixedKeyPage, ShrinkablePage, VarKeyPage, VarRecordPage

public abstract class BtreePage
extends java.lang.Object
implements Streamable

Abstract class containing the main logic for searching and updating a Btree. It searches and updates the structure of the pages that make up the tree. Pages are obtained by calls on the associated BtreePageSource. Searching and updating of the entries on a given page is handled by the subclass for the specific page format.

There are two types of normal pages: FixedKeyPage and VarKeyPage. A given btree will have either all FixedKeyPages or all VarKeyPages, depending on the key type. These are kept in a tree structure where leaf pages contain the actual data and intermediate pages contain pageIds of the pages on the level below.

The exception to this is BigKeyPages, which may coexist with VarKeyPages in the same btree. These are used when a key is encountered whose length is such that the key plus its data would take up more than one-third the available space on a page (for a btree with MOFID data items this would be a key longer than 670 bytes). All BigKeyPages are kept on a single chain attached to the root on the right.

Version:
1.0
Author:
Dana Bergen

Field Summary
 byte[] pageBuffer
           
 byte[] pageId
           
 
Constructor Summary
BtreePage()
          Construct an empty BtreePage.
 
Method Summary
protected  byte compare(byte[] key, int entryNum)
          Compares the key with that of the specified entry.
protected  byte compareData(byte[] data, int entryNum)
           
 int consistencyCheck(java.io.PrintWriter out)
           
 void dumpPage(java.io.PrintWriter out)
          Print BtreePage contents for debugging.
 void dumpPageBuffer(java.io.PrintWriter out)
          Print raw page buffer contents for debugging.
 void dumpPageEntries(java.io.PrintWriter out)
          Print BtreePage entries for debugging.
 void dumpPageHeader(java.io.PrintWriter out)
          Print BtreePage header for debugging.
 void dumpTree(java.io.PrintWriter out)
          Print tree starting from this page for debugging.
 byte[] get(byte[] key)
          Retrieves the value associated with the given key.
 org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult getLocation(byte[] key)
          Finds the first entry associated with the given key, navigating down the btree from this page.
 void init(Btree btree, byte[] pageId, byte[] pageBuffer, boolean isNew)
          Initialize a newly-instantiated or recycled BtreePage.
 void makeRoot()
           
 void put(byte[] key, byte[] data, byte operation, int index)
          Add an entry to the btree, navigating down from this page.
 void put(byte[] key, byte[] data, byte operation, int index, org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
          Add an entry to the btree, navigating down from this page.
 void read(java.io.InputStream in)
          (Streamable Interface) Populate the pageBuffer from the InputStream.
 boolean remove(byte[] key)
          Remove all entries from the btree that match the given key.
 boolean remove(byte[] key, byte[] data)
          Remove the first entry encountered that matches the key/value pair.
 boolean remove(byte[] key, int index)
          Remove the item matching the key at the indexed position.
protected  org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry split(org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry entry, int entryNum, org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
           
 void store()
          Write BtreePage header data to the page buffer.
 void uninit()
           
 void write(java.io.OutputStream out)
          (Streamable Interface) Write this page to the OutputStream.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

pageBuffer

public byte[] pageBuffer

pageId

public byte[] pageId
Constructor Detail

BtreePage

public BtreePage()
Construct an empty BtreePage. All the real work is done in init().

Method Detail

init

public void init(Btree btree,
                 byte[] pageId,
                 byte[] pageBuffer,
                 boolean isNew)
          throws StorageException
Initialize a newly-instantiated or recycled BtreePage. Note that the isNew parameter pertains to whether a new page is being added to the btree, not to whether this BtreePage object is new or recycled.

Parameters:
btree - Btree to which this page belongs
pageId - page ID in byte array
pageBuffer - page buffer
isNew - is this page new to the btree
Throws:
StorageException

store

public void store()
Write BtreePage header data to the page buffer.


read

public void read(java.io.InputStream in)
          throws StorageException
(Streamable Interface) Populate the pageBuffer from the InputStream. The page is not usable until init() has also been called. This is done in pageSource.getPage because it requires a reference to the Btree.

Specified by:
read in interface Streamable
Parameters:
in - InputStream to read from
Throws:
StorageException

write

public void write(java.io.OutputStream out)
           throws StorageException
(Streamable Interface) Write this page to the OutputStream.

Specified by:
write in interface Streamable
Parameters:
out - OutputStream to write page to
Throws:
StorageException

uninit

public void uninit()

put

public void put(byte[] key,
                byte[] data,
                byte operation,
                int index)
         throws StorageException
Add an entry to the btree, navigating down from this page.

Parameters:
key - byte array containing key
data - byte array containing data
Throws:
StorageException

put

public void put(byte[] key,
                byte[] data,
                byte operation,
                int index,
                org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
         throws StorageException
Add an entry to the btree, navigating down from this page.

Parameters:
key - byte array containing key
data - byte array containing data
resultPosition - location of inserted element is recorded in case this parameter is not null and the oparation to perform is insert (add).
Throws:
StorageException

get

public byte[] get(byte[] key)
           throws StorageException
Retrieves the value associated with the given key.

Parameters:
key - key to find the entry for
Returns:
the data associated with the passed-in key, or null if it was not found.
Throws:
StorageException

getLocation

public org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult getLocation(byte[] key)
                                                                           throws StorageException
Finds the first entry associated with the given key, navigating down the btree from this page. Recursively calls itself on its children until a leaf page is reached.

Parameters:
key - key to find the entry for
Returns:
SearchResult pointing to the entry. If no match was found, SearchResult.matched will be false.
Throws:
StorageException

remove

public boolean remove(byte[] key)
               throws StorageException
Remove all entries from the btree that match the given key.

Parameters:
key - the key to be matched
Returns:
boolean indicating whether a match was found
Throws:
StorageException

remove

public boolean remove(byte[] key,
                      byte[] data)
               throws StorageException
Remove the first entry encountered that matches the key/value pair.

Parameters:
key - the key to be matched
data - the data value to be matched
Returns:
boolean indicating whether a match was found
Throws:
StorageException

remove

public boolean remove(byte[] key,
                      int index)
               throws StorageException
Remove the item matching the key at the indexed position.

Parameters:
key - the key to be matched
index - position within key's entries of the target entry
Returns:
boolean indicating whether a match was found
Throws:
StorageException

split

protected org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry split(org.netbeans.mdr.persistence.btreeimpl.btreeindex.BtreePage.BtreeEntry entry,
                                                                                       int entryNum,
                                                                                       org.netbeans.mdr.persistence.btreeimpl.btreeindex.SearchResult resultPosition)
                                                                                throws StorageException
Throws:
StorageException

compare

protected byte compare(byte[] key,
                       int entryNum)
Compares the key with that of the specified entry. Just handles one special case and then calls btree.keyInfo.compare().

Parameters:
key - search key
entryNum - entry number of target entry
Returns:
EntryTypeInfo.EQUAL if the two keys are equal EntryTypeInfo.GREATER if search key is greater than entry's key EntryTypeInfo.LESS if search key is less than entry's key

compareData

protected byte compareData(byte[] data,
                           int entryNum)

makeRoot

public void makeRoot()

dumpPage

public void dumpPage(java.io.PrintWriter out)
              throws StorageException
Print BtreePage contents for debugging.

Parameters:
out - PrintWriter to print to
Throws:
StorageException

dumpPageHeader

public void dumpPageHeader(java.io.PrintWriter out)
Print BtreePage header for debugging.

Parameters:
out - PrintWriter to print to

dumpPageEntries

public void dumpPageEntries(java.io.PrintWriter out)
                     throws StorageException
Print BtreePage entries for debugging.

Parameters:
out - PrintWriter to print to
Throws:
StorageException

dumpPageBuffer

public void dumpPageBuffer(java.io.PrintWriter out)
Print raw page buffer contents for debugging.

Parameters:
out - PrintWriter to print to

dumpTree

public void dumpTree(java.io.PrintWriter out)
              throws StorageException
Print tree starting from this page for debugging.

Parameters:
out - PrintWriter to print to
Throws:
StorageException

consistencyCheck

public int consistencyCheck(java.io.PrintWriter out)
                     throws StorageException
Throws:
StorageException


Copyright © 2005-2011 Apache Software Foundation. All Rights Reserved.