iglu.util
Class FileBTree

java.lang.Object
  |
  +--iglu.util.FileBTree

public class FileBTree

extends java.lang.Object

A B-Tree index file which contains both the index and the data which the index points to. Implements the B-Tree described in Cormen, except that a value pointer is attached to each entry in the tree. Whenever a new node or value is needed, the space is just allocated off the end of the file. It uses safe flags to indicate whether or not a node has been appropriatly written out.

File Structure:

• 0-3 (int): Number of elements per node
• 4-7 (int): Number of bytes in a key
• 8-15 (long): status bits
  • 0: 1=Safe, 0=Unsafe
• 16-19 (int): t
• 20-27 (long): Root node
• 28-35 (long): Number of Records
• 36-199: Reserved Space
• First Node always resides at 200.

Block Entry Structure

• 0-7 (long): Status bits
  • 0: 1=valid, 0=invalid
  • 1: 1=safe, 0=unsafe
  • 3: 1=is leaf, 0=is not a leaf
• 8-11 (int): Number of valid keys
• (keySize + 24)*nodeSize: the entries

Index Entry Structure

• 0-7 (long): Status Bits
  • 0: 1=Valid, 0=Invalid
  • 2-7: Reserved
• keySize bytes in the key
• next 8 (long): Pointer to value
• next 8 (long): Pointer to next node

Value entry

• 0-3 (int): length of value
• the entry itself

Version:

1.0

Author:

Travis Bauer

Nested Class Summary

class	FileBTree.Entry
class	FileBTree.Node
private class	FileBTree.ValueIterator

Field Summary

static long	B_ISLEAF Bitmask for if a block is a leaf
static long	B_SAFE Bitmask for a block's safety bit
static long	B_VALID Bitmask for a block's validity bit
static long	F_SAFE bitmask for the file's safety status bit
protected java.io.RandomAccessFile	file pointer to the actual file
protected java.lang.String	filename name of the file
static long	FIRSTNODE_LOC Location of where the first node is stored
static long	FSTATUSFLAGS_LOC Location of the status flag for the file
static long	I_VALID Bitmask for if an entry is value
protected int	keySize Number of bytes in a key
static long	KEYSIZE_LOC Location of the number of keys per node
protected java.util.HashMap	nodes A hash map of the nodes
protected int	nodeSize Number of keys per node (2*t-1)
static long	NODESIZE_LOC Location of the size of a node
protected long	numRecords Number of records in this file
static long	NUMRECORDS_LOC Location of the number of records
protected long	rootPointer Pointer to the root node
static long	ROOTPTR_LOC Location of the root pointer
protected long	statusBits Status flags for this file
protected int	t t parameter
static long	T_LOC Location of the t parameter

Constructor Summary

FileBTree(java.lang.String filename)

FileBTree(java.lang.String filename, int t, int keySize)

Method Summary

static java.io.Serializable	bytesToObj(byte[] b)
void	close()
static int	compBytes(byte[] a, byte[] b)
protected void	createFile()
protected FileBTree.Node	createNewNodeFromFile()
boolean	delete(byte[] key)
protected boolean	delete(byte[] key, long nodePtr)
boolean	delete(long key)
boolean	delete(java.lang.Long key)
boolean	delete(java.io.Serializable key)
boolean	delete(java.lang.String key)
protected void	finalize()
protected void	flushNodes()
protected FileBTree.Node	getNewNode()
protected FileBTree.Node	getNode(long ptr)
long	getNumRecords()
long	getRootPointer()
protected byte[]	getValue(long ptr)
void	insert(byte[] key, byte[] value)
void	insert(byte[] key, java.io.Serializable value)
void	insert(long key, byte[] value)
protected void	insert(long nodePtr, byte[] key, byte[] value)
void	insert(long key, java.io.Serializable value)
void	insert(java.io.Serializable key, byte[] value)
void	insert(java.io.Serializable key, java.io.Serializable value)
void	insert(java.lang.String key, byte[] value)
void	insert(java.lang.String key, java.io.Serializable value)
protected void	insertNonfull(FileBTree.Node x, byte[] key, byte[] value)
protected byte[]	longToBytes(long l)
byte[]	lookup(byte[] key)
protected byte[]	lookup(byte[] key, long nodePtr)
byte[]	lookup(long key)
byte[]	lookup(java.io.Serializable key)
byte[]	lookup(java.lang.String key)
java.io.Serializable	lookupObject(byte[] key)
java.io.Serializable	lookupObject(long key)
java.io.Serializable	lookupObject(java.io.Serializable key)
java.io.Serializable	lookupObject(java.lang.String key)
static void	main(java.lang.String[] argv)
static byte[]	objectToBytes(java.io.Serializable o)
protected void	openFile()
protected FileBTree.Node	readNodeFromFile(long ptr)
protected byte[]	readValueFromFile(long ptr)
byte[]	sizeKey(byte[] key)
protected void	splitChild(FileBTree.Node x, int i, FileBTree.Node y)
java.lang.String	toString()
java.util.Iterator	valueIterator()
protected void	writeNodeStatusSafe(FileBTree.Node n)
protected void	writeNodeToFile(FileBTree.Node n, boolean safe)
protected long	writeValue(byte[] value)
protected void	writeValue(long ptr, byte[] value)
protected void	writeValueToFile(long ptr, byte[] value)

Methods inherited from class java.lang.Object

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

Field Detail

NODESIZE_LOC

public static final long NODESIZE_LOC

Location of the size of a node

See Also:

Constant Field Values

KEYSIZE_LOC

public static final long KEYSIZE_LOC

Location of the number of keys per node

See Also:

Constant Field Values

FSTATUSFLAGS_LOC

public static final long FSTATUSFLAGS_LOC

Location of the status flag for the file

See Also:

Constant Field Values

T_LOC

public static final long T_LOC

Location of the t parameter

See Also:

Constant Field Values

ROOTPTR_LOC

public static final long ROOTPTR_LOC

Location of the root pointer

See Also:

Constant Field Values

NUMRECORDS_LOC

public static final long NUMRECORDS_LOC

Location of the number of records

See Also:

Constant Field Values

FIRSTNODE_LOC

public static final long FIRSTNODE_LOC

Location of where the first node is stored

See Also:

Constant Field Values

F_SAFE

public static final long F_SAFE

bitmask for the file's safety status bit

See Also:

Constant Field Values

B_VALID

public static final long B_VALID

Bitmask for a block's validity bit

See Also:

Constant Field Values

B_SAFE

public static final long B_SAFE

Bitmask for a block's safety bit

See Also:

Constant Field Values

B_ISLEAF

public static final long B_ISLEAF

Bitmask for if a block is a leaf

See Also:

Constant Field Values

I_VALID

public static final long I_VALID

Bitmask for if an entry is value

See Also:

Constant Field Values

filename

protected java.lang.String filename

name of the file

file

protected java.io.RandomAccessFile file

pointer to the actual file

t

protected int t

t parameter

nodeSize

protected int nodeSize

Number of keys per node (2*t-1)

keySize

protected int keySize

Number of bytes in a key

statusBits

protected long statusBits

Status flags for this file

numRecords

protected long numRecords

Number of records in this file

rootPointer

protected long rootPointer

Pointer to the root node

nodes

protected java.util.HashMap nodes

A hash map of the nodes

Constructor Detail

FileBTree

public FileBTree(java.lang.String filename,
                 int t,
                 int keySize)

FileBTree

public FileBTree(java.lang.String filename)

Method Detail

close

public void close()

valueIterator

public java.util.Iterator valueIterator()

flushNodes

protected void flushNodes()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

createFile

protected void createFile()

openFile

protected void openFile()

getRootPointer

public long getRootPointer()

getNumRecords

public long getNumRecords()

lookup

public byte[] lookup(byte[] key)

lookup

public byte[] lookup(long key)

lookup

public byte[] lookup(java.lang.String key)

lookup

public byte[] lookup(java.io.Serializable key)

lookupObject

public java.io.Serializable lookupObject(byte[] key)

lookupObject

public java.io.Serializable lookupObject(long key)

lookupObject

public java.io.Serializable lookupObject(java.lang.String key)

lookupObject

public java.io.Serializable lookupObject(java.io.Serializable key)

lookup

protected byte[] lookup(byte[] key,
                        long nodePtr)

delete

public boolean delete(java.lang.String key)

delete

public boolean delete(java.lang.Long key)

delete

public boolean delete(long key)

delete

public boolean delete(byte[] key)

delete

public boolean delete(java.io.Serializable key)

delete

protected boolean delete(byte[] key,
                         long nodePtr)

getNewNode

protected FileBTree.Node getNewNode()

createNewNodeFromFile

protected FileBTree.Node createNewNodeFromFile()

writeNodeToFile

protected void writeNodeToFile(FileBTree.Node n,
                               boolean safe)

writeNodeStatusSafe

protected void writeNodeStatusSafe(FileBTree.Node n)

getNode

protected FileBTree.Node getNode(long ptr)

readNodeFromFile

protected FileBTree.Node readNodeFromFile(long ptr)

getValue

protected byte[] getValue(long ptr)

readValueFromFile

protected byte[] readValueFromFile(long ptr)

writeValue

protected long writeValue(byte[] value)

writeValue

protected void writeValue(long ptr,
                          byte[] value)

writeValueToFile

protected void writeValueToFile(long ptr,
                                byte[] value)

splitChild

protected void splitChild(FileBTree.Node x,
                          int i,
                          FileBTree.Node y)

insert

public void insert(byte[] key,
                   byte[] value)

insert

public void insert(long key,
                   byte[] value)

insert

public void insert(java.lang.String key,
                   byte[] value)

insert

public void insert(java.io.Serializable key,
                   byte[] value)

insert

public void insert(byte[] key,
                   java.io.Serializable value)

insert

public void insert(long key,
                   java.io.Serializable value)

insert

public void insert(java.lang.String key,
                   java.io.Serializable value)

insert

public void insert(java.io.Serializable key,
                   java.io.Serializable value)

insert

protected void insert(long nodePtr,
                      byte[] key,
                      byte[] value)

insertNonfull

protected void insertNonfull(FileBTree.Node x,
                             byte[] key,
                             byte[] value)

finalize

protected void finalize()
                 throws java.io.IOException

Overrides:

finalize in class java.lang.Object

java.io.IOException

compBytes

public static int compBytes(byte[] a,
                            byte[] b)

longToBytes

protected byte[] longToBytes(long l)

bytesToObj

public static java.io.Serializable bytesToObj(byte[] b)

sizeKey

public byte[] sizeKey(byte[] key)

objectToBytes

public static byte[] objectToBytes(java.io.Serializable o)

main

public static void main(java.lang.String[] argv)