jdbm.btree
Class BPage

java.lang.Object
  extended by jdbm.btree.BPage
All Implemented Interfaces:
java.io.Serializable, Serializer

public final class BPage
extends java.lang.Object
implements Serializer

Page of a Btree.

The page contains a number of key-value pairs. Keys are ordered to allow dichotomic search.

If the page is a leaf page, the keys and values are user-defined and represent entries inserted by the user.

If the page is non-leaf, each key represents the greatest key in the underlying BPages and the values are recids pointing to the children BPages. The only exception is the rightmost BPage, which is considered to have an "infinite" key value, meaning that any insert will be to the left of this pseudo-key

Version:
$Id: BPage.java,v 1.6 2003/09/21 15:46:59 boisvert Exp $
Author:
Alex Boisvert
See Also:
Serialized Form

Nested Class Summary
(package private) static class BPage.Browser
          PRIVATE INNER CLASS Browser to traverse leaf BPages.
(package private) static class BPage.InsertResult
          STATIC INNER CLASS Result from insert() method call
(package private) static class BPage.RemoveResult
          STATIC INNER CLASS Result from remove() method call
 
Field Summary
(package private)  BTree _btree
          Parent B+Tree.
protected  long[] _children
          Children pages (recids) associated with keys.
protected  int _first
          Index of first used item at the page
protected  boolean _isLeaf
          Flag indicating if this is a leaf BPage.
protected  java.lang.Object[] _keys
          Keys of children nodes
protected  long _next
          Next leaf BPage (only if this BPage is a leaf)
protected  long _previous
          Previous leaf BPage (only if this BPage is a leaf)
protected  long _recid
          This BPage's record ID in the PageManager.
protected  java.lang.Object[] _values
          Values associated with keys.
(package private) static long serialVersionUID
          Version id for serialization.
 
Constructor Summary
BPage()
          No-argument constructor used by serialization.
BPage(BTree btree, boolean isLeaf)
          Overflow page constructor.
BPage(BTree btree, BPage root, BPage overflow)
          Root page overflow constructor
BPage(BTree btree, java.lang.Object key, java.lang.Object value)
          Root page (first insert) constructor.
 
Method Summary
(package private)  void assertConsistencyRecursive(int height)
          Recursively assert the ordering of the BPage entries on this page and sub-pages.
(package private)  BPage childBPage(int index)
          Return the child BPage at given index.
 java.lang.Object deserialize(byte[] serialized)
          Deserialize the content of an object from a byte array.
(package private)  void dumpRecursive(int height, int level)
          Recursively dump the state of the BTree on screen.
(package private)  TupleBrowser find(int height, java.lang.Object key)
          Find the object associated with the given key.
(package private)  TupleBrowser findFirst()
          Find first entry and return a browser positioned before it.
(package private)  java.lang.Object getLargestKey()
          Get largest key under this BPage.
(package private)  BPage.InsertResult insert(int height, java.lang.Object key, java.lang.Object value, boolean replace)
          Insert the given key and value.
(package private)  boolean isEmpty()
          Return true if BPage is empty.
(package private)  boolean isFull()
          Return true if BPage is full.
(package private) static byte[] readByteArray(java.io.ObjectInput in)
           
(package private)  BPage.RemoveResult remove(int height, java.lang.Object key)
          Remove the entry associated with the given key.
 byte[] serialize(java.lang.Object obj)
          Serialize the content of an object into a byte array.
(package private) static void writeByteArray(java.io.ObjectOutput out, byte[] buf)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

static final long serialVersionUID
Version id for serialization.

See Also:
Constant Field Values

_btree

transient BTree _btree
Parent B+Tree.


_recid

protected transient long _recid
This BPage's record ID in the PageManager.


_isLeaf

protected boolean _isLeaf
Flag indicating if this is a leaf BPage.


_keys

protected java.lang.Object[] _keys
Keys of children nodes


_values

protected java.lang.Object[] _values
Values associated with keys. (Only valid if leaf BPage)


_children

protected long[] _children
Children pages (recids) associated with keys. (Only valid if non-leaf BPage)


_first

protected int _first
Index of first used item at the page


_previous

protected long _previous
Previous leaf BPage (only if this BPage is a leaf)


_next

protected long _next
Next leaf BPage (only if this BPage is a leaf)

Constructor Detail

BPage

public BPage()
No-argument constructor used by serialization.


BPage

BPage(BTree btree,
      BPage root,
      BPage overflow)
throws java.io.IOException
Root page overflow constructor

Throws:
java.io.IOException

BPage

BPage(BTree btree,
      java.lang.Object key,
      java.lang.Object value)
throws java.io.IOException
Root page (first insert) constructor.

Throws:
java.io.IOException

BPage

BPage(BTree btree,
      boolean isLeaf)
throws java.io.IOException
Overflow page constructor. Creates an empty BPage.

Throws:
java.io.IOException
Method Detail

getLargestKey

java.lang.Object getLargestKey()
Get largest key under this BPage. Null is considered to be the greatest possible key.


isEmpty

boolean isEmpty()
Return true if BPage is empty.


isFull

boolean isFull()
Return true if BPage is full.


find

TupleBrowser find(int height,
                  java.lang.Object key)
            throws java.io.IOException
Find the object associated with the given key.

Parameters:
height - Height of the current BPage (zero is leaf page)
key - The key
Returns:
TupleBrowser positionned just before the given key, or before next greater key if key isn't found.
Throws:
java.io.IOException

findFirst

TupleBrowser findFirst()
                 throws java.io.IOException
Find first entry and return a browser positioned before it.

Returns:
TupleBrowser positionned just before the first entry.
Throws:
java.io.IOException

insert

BPage.InsertResult insert(int height,
                          java.lang.Object key,
                          java.lang.Object value,
                          boolean replace)
                    throws java.io.IOException
Insert the given key and value.

Since the Btree does not support duplicate entries, the caller must specify whether to replace the existing value.

Parameters:
height - Height of the current BPage (zero is leaf page)
key - Insert key
value - Insert value
replace - Set to true to replace the existing value, if one exists.
Returns:
Insertion result containing existing value OR a BPage if the key was inserted and provoked a BPage overflow.
Throws:
java.io.IOException

remove

BPage.RemoveResult remove(int height,
                          java.lang.Object key)
                    throws java.io.IOException
Remove the entry associated with the given key.

Parameters:
height - Height of the current BPage (zero is leaf page)
key - Removal key
Returns:
Remove result object
Throws:
java.io.IOException

childBPage

BPage childBPage(int index)
           throws java.io.IOException
Return the child BPage at given index.

Throws:
java.io.IOException

readByteArray

static byte[] readByteArray(java.io.ObjectInput in)
                     throws java.io.IOException
Throws:
java.io.IOException

writeByteArray

static void writeByteArray(java.io.ObjectOutput out,
                           byte[] buf)
                    throws java.io.IOException
Throws:
java.io.IOException

dumpRecursive

void dumpRecursive(int height,
                   int level)
             throws java.io.IOException
Recursively dump the state of the BTree on screen. This is used for debugging purposes only.

Throws:
java.io.IOException

assertConsistencyRecursive

void assertConsistencyRecursive(int height)
                          throws java.io.IOException
Recursively assert the ordering of the BPage entries on this page and sub-pages. This is used for testing purposes only.

Throws:
java.io.IOException

deserialize

public java.lang.Object deserialize(byte[] serialized)
                             throws java.io.IOException
Deserialize the content of an object from a byte array.

Specified by:
deserialize in interface Serializer
Parameters:
serialized - Byte array representation of the object
Returns:
deserialized object
Throws:
java.io.IOException

serialize

public byte[] serialize(java.lang.Object obj)
                 throws java.io.IOException
Serialize the content of an object into a byte array.

Specified by:
serialize in interface Serializer
Parameters:
obj - Object to serialize
Returns:
a byte array representing the object's state
Throws:
java.io.IOException


Cees de Groot (C) 2000-2001. All rights reserved http://jdbm.sourceforge.net