| java.lang.Object
 com.quadcap.sql.index.Bnode
| Bnode | | public class Bnode (Code) | | This class represents a node in the btree.
Things to think about:
- Key Compression using dictionary? With a large enough node, say
4 or 8 k, you could perform a block compression
- Key Endianness (X.500 keys are LSB, most others are MSB)
- Large data stored in overflow areas (blockstream)
- Thread-safeness
- Improve block garbage collection (it appears that some deleted
keys aren't properly counted as garbage!)
author:
Stan Bailes |
| Field Summary | |
| final static int | BNODE_MAGICF
| | final static int | BNODE_MAGICV
| | final static int | IS_LEAF
| | final public static int | REF_SIZE
The number of octets in the representation of a reference to
a byte offset in the data area of this block. | | long | blockRef
| | final static int | fCount
Number of key/data pairs in this node. | | final static int | fDataBOS
Bottom of data area -- grows downward. | | final static int | fFlags
| | final static int | fGarbage
Amount of space that could be reclaimed by repacking the
node. | | final static int | fIndices
Start of key indices. | | final static int | fParent
| | BlockFile | file
| | final static boolean | paranoid
| | Btree | tree
|
| Constructor Summary | |
| public | Bnode(Btree tree, long blockRef)
Construct a node from a buffer. |
| Method Summary | |
| final static long | blockRef(Block b, int index)
| | final static int | bsearch(Block b, Comparator c, byte[] key, int klen, int lo, int hi)
Perform a binary search of the keys in the specified block, searching
for the given key. | | final int | bsearch(Block b, byte[] key, int klen)
Perform a binary search of the keys in the specified block, searching
for the given key. | | final static int | capacity(Block b)
Return the number of available bytes in the buffer, not including
space that could be made available by performing a garbage collection. | | final void | checkBlock(Block b)
| | final void | checkMagic()
| | final int | checkSpace(Block b, int index, int klen, int dlen, boolean replace)
Determine if there is room in the block for a new key/data pair.
Parameters:
b - the block to operate on
Parameters:
index - the index of the key that is being replaced,if replace is true.
Parameters:
klen - the search key length
Parameters:
dlen - the length of the data associated with the key
Parameters:
replace - true if an existing key/data pair is tobe replaced by the new key, false otherwise. | | final static byte[] | dataAtPos(Block b, int index)
Given a block and a key index, return the data for that index as a new
byte array. | | final static int | dataAtPos(Block b, int index, int koff, byte[] data, int off, int len)
| | final public static String | databytes(byte[] b)
Represent strings as having a length other than 4, while representing
integers as only of length 4 bytes. | | final int | debugcheckSpace(Block b, int index, int klen, int dlen, boolean replace)
| | final public boolean | delete(byte[] key)
Implement the delete operation. | | final boolean | delete(Block b, byte[] key)
Recursive implementation of delete(key). | | final boolean | deleteKeyAtPos(Block b, int index, boolean skipNewLow)
Delete the specified key. | | final void | display(PrintStream os, boolean recursive)
For debugging purposes, write a human readable version of this
Bnode to the specified stream. | | final void | display(PrintStream os, PrintStream er, boolean recursive)
| | final void | display(Block b, PrintStream os, boolean recursive)
| | final void | display(Block b, PrintStream os, PrintStream er, boolean recursive)
| | final static int | existingKeyLength(Block b, int index)
Compute the total length of an existing key data pair, including
both key and data length fields. | | final void | forgetKeyAtPos(Block b, int index)
This function is scary. | | final public void | free()
Free the resources associated with this block. | | final void | gc(Block b)
Reclaim the data space occupied by deleted keys. | | final public byte[] | get(byte[] key, int klen)
Implement the get operation. | | final byte[] | get(Block b, byte[] key, int klen)
A helper function to perform a single-level of the recursive search. | | final Block | getBlock(long blockNum)
| | final Block | getBlock()
| | final static int | getBos(Block b)
Return the value of the count field. | | final static int | getBytes(Block b, int pos, byte[] buf, int[] lenret)
| | final public static int | getCount(Block b)
Return the value of the bos field. | | final public static boolean | getFlag(Block b, int mask)
Return the boolean value of a specified flag. | | final public static int | getFlags(Block b)
Return the value of the flags field. | | final public static int | getGarbage(Block b)
Return the value of the garbage field. | | final public static boolean | getKeyAndData(Block b, int index, byte[] k, byte[] d, int[] lengths)
Given a block and a key index, return the key for that index as a new
byte array.
Parameters:
b - the block on which to operate.
Parameters:
index - the index of the item for which the key is to be retrieved
Parameters:
buf - the buffer into which the key bytes should be places
Parameters:
off - the offset into the buffer
Parameters:
len - the maximum number of bytes to write to the buffer the number of bytes returned, if sucessful. | | final static int | getKeyEnd(Block b, int keypos)
Find the length of the specified key, as well as the byte offset
to the start of the key.
Parameters:
b - the B-node
Parameters:
keypos - the buffer offset where the key/data pair starts. | | final static int | getKeyIndex(Block b, int index)
Return the byte offset of the specified key/data pair. | | final static int | getKeyLen(Block b, int keypos, int[] keystart)
Find the length of the specified key, as well as the byte offset
to the start of the key. | | final static int | getKeyLen(Block b, int keypos)
Find the length of the specified key, as well as the byte offset
to the start of the key.
Parameters:
b - the B-node
Parameters:
keypos - the buffer offset where the key/data pair starts. | | final public static long | getParent(Block b)
Return the value of the parent field. | | final Block | getSearchBlock(Block b, int bs)
| | final static int | index(int pos)
| | final void | init(Block b, boolean isLeaf)
Initialize an empty BNode. | | final void | init(boolean f)
| | final static int | insertKeyData(Block b, byte[] key, int klen, byte[] data, int doff, int dlen)
Insert a key/data pair at the bottom of the data area and
return its offset. | | final public static boolean | isLeaf(Block b)
Return the value of the IS_LEAF flag. | | final static byte[] | keyAtPos(Block b, int index)
Given a block and a key index, return the key for that index as a new
byte array. | | final static int | keyCompareAtPos(Comparator c, byte[] key, int klen, Block b, int index)
Perform a key comparison with the specified key in the block. | | final static String | keybytes(byte[] key)
Since this is used for displaying the key, we attempt to return the
string itself, as long as it is composed only of printable characters. | | final static String | keybytes(byte[] key, int off, int len)
| | final static long | longDataAtPos(Block b, int index)
Given a block and a key index, return the data for that index as
a long. | | final static void | moveKeys(Block b, int from, int to, int length)
Helper function to move key indices around when adding or deleting
keys. | | final boolean | newLow(Block b, byte[] prevLow)
When an operation results in a change in the smallest key in a block,
it is necessary to inform the parent block of the change, since the
parent block key for this block is required to be the key of the
smallest item in this block.
Parameters:
b - the block containing the new lowest key
Parameters:
prevLow - the key which was previously the lowest key. | | final void | propogateSplit(Block[] ba)
After the split operation, propagate information up the tree to
the parent block about the newly created block and the new key
distribution. | | final public boolean | set(byte[] key, int klen, byte[] data, int doff, int dlen, boolean insOk, boolean updOk)
Implement the set operation. | | final boolean | set(Block b, byte[] key, int klen, byte[] data, int doff, int dlen, boolean insOk, boolean updOk)
Recursive implementation of set(key, data).
Precondition: The caller must already have a write-lock on
b. | | final public static void | setBos(Block b, int bos)
Set the value of the bos field. | | final public static void | setCount(Block b, int count)
Set the value of the count field. | | final public static void | setFlag(Block b, int mask, boolean val)
Set a specified boolean flag. | | final public static void | setFlags(Block b, int flags)
Set the value of the flags field. | | final public static void | setGarbage(Block b, int g)
Set the value of the garbage field. | | final Block | setKey(Block b, int index, byte[] key, int klen, byte[] data, int doff, int dlen, boolean replace)
Insert or replace a key in the specified block, which may or may
not be a leaf block. | | final boolean | setKeyAtPos(Block b, int index, byte[] key, int klen, byte[] data, int doff, int dlen, boolean replace)
Given a block and a key position, insert a new key/data pair
immediately at the specified position, returning true if the
key/data fit in the block. | | final static void | setKeyIndex(Block b, int index, int val)
Set the byte offset for the specified key/data pair. | | final public static void | setLeaf(Block b, boolean v)
Set the value of the IS_LEAF flag. | | final public static void | setParent(Block b, long g)
Set the value of the parent field. | | public int | size()
Return the number of keys in this subtree. | | public int | size(Block b)
| | final void | split(Block[] ba)
Split this block, by creaing a new block and moving half of this
block's keys into the new block. | | final void | splitHelp(Block[] ba, long nbno)
| | final static int | totalLength(int len)
Compute the total number of bytes that will be required to store
the byte array 'b' plus its length code. | | final static int | writeLenLen(Block b, int bos, int len)
Write a length code for the specified length, working backwards in
the data area, and returning the new bottom of the data area. |
| BNODE_MAGICF | | final static int BNODE_MAGICF(Code) | | |
| BNODE_MAGICV | | final static int BNODE_MAGICV(Code) | | |
| IS_LEAF | | final static int IS_LEAF(Code) | | |
| REF_SIZE | | final public static int REF_SIZE(Code) | | The number of octets in the representation of a reference to
a byte offset in the data area of this block. Currently,
bnode blocks can't be larger than 65536 because of the
two byte ref size.
|
| fCount | | final static int fCount(Code) | | Number of key/data pairs in this node.
|
| fDataBOS | | final static int fDataBOS(Code) | | Bottom of data area -- grows downward.
|
| fFlags | | final static int fFlags(Code) | | Flags
|
| fGarbage | | final static int fGarbage(Code) | | Amount of space that could be reclaimed by repacking the
node. When keys are deleted, we don't immediately remove
the key/data pair in the data area. Instead, we remove the
pointer the pair from the key index list, and record (here)
the size of the key/data pair. Later, when the block becomes
full, we reclaim this space by repacking the data area to
eliminate the holes.
|
| fIndices | | final static int fIndices(Code) | | Start of key indices.
|
| fParent | | final static int fParent(Code) | | |
| paranoid | | final static boolean paranoid(Code) | | |
| Bnode | | public Bnode(Btree tree, long blockRef)(Code) | | Construct a node from a buffer.
Parameters:
tree - the Btree containing this node
Parameters:
blockRef - the block number in file of this node. |
| blockRef | | final static long blockRef(Block b, int index) throws IOException(Code) | | Return the data for a specified key as an integer
|
| bsearch | | final static int bsearch(Block b, Comparator c, byte[] key, int klen, int lo, int hi) throws IOException(Code) | | Perform a binary search of the keys in the specified block, searching
for the given key. If the key is found in the block, return the
index of the matching key. If the key isn't
found, return < 0, and for the key index which is the smallest
existing key greater than the given key, return
0 - (index+1).
Parameters:
b - the block to be searched.
Parameters:
key - the search key
Parameters:
lo - index of smallest element in search region
Parameters:
hi - index of largest element in search region if found, the index of the matching key/data pair. If notfound, return the index where the data would be foundas an expression of the form:0 - (index + 1)
|
| bsearch | | final int bsearch(Block b, byte[] key, int klen) throws IOException(Code) | | Perform a binary search of the keys in the specified block, searching
for the given key. If the key is found in the block, return the
index of the matching key. If the key isn't
found, return < 0, and for the key index which is the smallest
existing key greater than the given key, return
0 - (index+1).
Parameters:
b - the block to be searched.
Parameters:
key - the search key if found, the index of the matching key/data pair. If notfound, return the index where the data would be foundas an expression of the form:0 - (index + 1)
|
| capacity | | final static int capacity(Block b)(Code) | | Return the number of available bytes in the buffer, not including
space that could be made available by performing a garbage collection.
|
| checkSpace | | final int checkSpace(Block b, int index, int klen, int dlen, boolean replace)(Code) | | Determine if there is room in the block for a new key/data pair.
Parameters:
b - the block to operate on
Parameters:
index - the index of the key that is being replaced,if replace is true.
Parameters:
klen - the search key length
Parameters:
dlen - the length of the data associated with the key
Parameters:
replace - true if an existing key/data pair is tobe replaced by the new key, false otherwise. negative number if there is no room for the new data.zero if there is room for the new data. positive number if there would be room after a garbagecollection. Included in this calculation is the deletionof the key being replaced, if replace is true. |
| dataAtPos | | final static byte[] dataAtPos(Block b, int index)(Code) | | Given a block and a key index, return the data for that index as a new
byte array.
Parameters:
b - the block on which to operate.
Parameters:
index - the index of the item for which the data is to be retrieved the data for the key at the specified position in the node. |
| dataAtPos | | final static int dataAtPos(Block b, int index, int koff, byte[] data, int off, int len)(Code) | | |
| databytes | | final public static String databytes(byte[] b)(Code) | | Represent strings as having a length other than 4, while representing
integers as only of length 4 bytes.
Parameters:
b - the string of bytes to convert A string containing either a 4-byte integer conversion or astring 'keybytes' filter. |
| debugcheckSpace | | final int debugcheckSpace(Block b, int index, int klen, int dlen, boolean replace)(Code) | | |
| delete | | final public boolean delete(byte[] key) throws IOException(Code) | | Implement the delete operation.
Parameters:
key - the key |
| delete | | final boolean delete(Block b, byte[] key) throws IOException(Code) | | Recursive implementation of delete(key).
Parameters:
b - the block to be searched
Parameters:
key - the search key true if the key already existed before the delete,false otherwise. |
| deleteKeyAtPos | | final boolean deleteKeyAtPos(Block b, int index, boolean skipNewLow) throws IOException(Code) | | Delete the specified key.
true if the block is now empty, has been freed, and weshould avoid touching it... |
| display | | final void display(PrintStream os, boolean recursive) throws IOException(Code) | | For debugging purposes, write a human readable version of this
Bnode to the specified stream.
|
| existingKeyLength | | final static int existingKeyLength(Block b, int index)(Code) | | Compute the total length of an existing key data pair, including
both key and data length fields.
Parameters:
b - the block on which to operate.
Parameters:
index - the index of the item for which the data is to be retrieved the total number of data area bytes consumed by this item. |
| forgetKeyAtPos | | final void forgetKeyAtPos(Block b, int index)(Code) | | This function is scary. It accounts for the fact that we're about
to delete a key, by including the size of the key/data in the
node's garbage field, but it doesn't actually delete
the key. Be careful.
|
| free | | final public void free() throws IOException(Code) | | Free the resources associated with this block. If the block is a
non-leaf node, free the entire subtree.
|
| get | | final public byte[] get(byte[] key, int klen) throws IOException(Code) | | Implement the get operation.
Parameters:
key - the search key if the get succeeds, the data is returned as a byte array;if the get fails, null is returned. |
| get | | final byte[] get(Block b, byte[] key, int klen) throws IOException(Code) | | A helper function to perform a single-level of the recursive search.
Parameters:
b - the block to be searched.
Parameters:
key - the search key if found, the data, else null |
| getBos | | final static int getBos(Block b)(Code) | | Return the value of the count field.
|
| getBytes | | final static int getBytes(Block b, int pos, byte[] buf, int[] lenret)(Code) | | |
| getCount | | final public static int getCount(Block b)(Code) | | Return the value of the bos field.
|
| getFlag | | final public static boolean getFlag(Block b, int mask)(Code) | | Return the boolean value of a specified flag.
|
| getFlags | | final public static int getFlags(Block b)(Code) | | Return the value of the flags field.
|
| getGarbage | | final public static int getGarbage(Block b)(Code) | | Return the value of the garbage field.
|
| getKeyAndData | | final public static boolean getKeyAndData(Block b, int index, byte[] k, byte[] d, int[] lengths)(Code) | | Given a block and a key index, return the key for that index as a new
byte array.
Parameters:
b - the block on which to operate.
Parameters:
index - the index of the item for which the key is to be retrieved
Parameters:
buf - the buffer into which the key bytes should be places
Parameters:
off - the offset into the buffer
Parameters:
len - the maximum number of bytes to write to the buffer the number of bytes returned, if sucessful. If the bufferisn't big enough, we return a negative number '0 - k', where'k' is the actual key length. |
| getKeyEnd | | final static int getKeyEnd(Block b, int keypos)(Code) | | Find the length of the specified key, as well as the byte offset
to the start of the key.
Parameters:
b - the B-node
Parameters:
keypos - the buffer offset where the key/data pair starts. two 16-bit integers {start, len} encoded in a 32 bit int. |
| getKeyIndex | | final static int getKeyIndex(Block b, int index)(Code) | | Return the byte offset of the specified key/data pair.
Parameters:
b - the Bnode containing the key
Parameters:
index - the index of the specified key/data pair. |
| getKeyLen | | final static int getKeyLen(Block b, int keypos, int[] keystart)(Code) | | Find the length of the specified key, as well as the byte offset
to the start of the key.
Parameters:
b - the B-node
Parameters:
keypos - the buffer offset where the key/data pair starts.
Parameters:
keystart - an out parameter, used to return the bufferoffset where the actual key begins. |
| getKeyLen | | final static int getKeyLen(Block b, int keypos)(Code) | | Find the length of the specified key, as well as the byte offset
to the start of the key.
Parameters:
b - the B-node
Parameters:
keypos - the buffer offset where the key/data pair starts. the key length |
| getParent | | final public static long getParent(Block b)(Code) | | Return the value of the parent field.
|
| index | | final static int index(int pos)(Code) | | |
| init | | final void init(Block b, boolean isLeaf) throws IOException(Code) | | Initialize an empty BNode.
PRECONDITION:Hold lock on b.
Parameters:
b - the block to be initialized. |
| insertKeyData | | final static int insertKeyData(Block b, byte[] key, int klen, byte[] data, int doff, int dlen)(Code) | | Insert a key/data pair at the bottom of the data area and
return its offset. This method does NOT check the
capacity of the buffer -- it is assumed that the caller has
already ensured that enough space is available.
Parameters:
b - the block to operate on
Parameters:
key - the search key
Parameters:
data - the data associated with the key |
| isLeaf | | final public static boolean isLeaf(Block b)(Code) | | Return the value of the IS_LEAF flag.
|
| keyAtPos | | final static byte[] keyAtPos(Block b, int index)(Code) | | Given a block and a key index, return the key for that index as a new
byte array.
Parameters:
b - the block on which to operate.
Parameters:
index - the index of the item for which the key is to be retrieved |
| keyCompareAtPos | | final static int keyCompareAtPos(Comparator c, byte[] key, int klen, Block b, int index) throws IOException(Code) | | Perform a key comparison with the specified key in the block.
Parameters:
c - the compare function
Parameters:
key - the compare key
Parameters:
b - the block to be compared
Parameters:
index - the position of the key to be compared to the compare key the integer compare value (usu: -1, 0, 1) |
| keybytes | | final static String keybytes(byte[] key)(Code) | | Since this is used for displaying the key, we attempt to return the
string itself, as long as it is composed only of printable characters.
If it contains any "non-printable" characters, it is instead formatted
in hex/ascii dump form.
Parameters:
b - the bytes form of the key a displayable representation of the key. |
| keybytes | | final static String keybytes(byte[] key, int off, int len)(Code) | | |
| longDataAtPos | | final static long longDataAtPos(Block b, int index)(Code) | | Given a block and a key index, return the data for that index as
a long.
Parameters:
b - the block on which to operate.
Parameters:
index - the index of the item for which the data is to be retrieved the data for the key at the specified position in the node. |
| moveKeys | | final static void moveKeys(Block b, int from, int to, int length)(Code) | | Helper function to move key indices around when adding or deleting
keys.
|
| newLow | | final boolean newLow(Block b, byte[] prevLow) throws IOException(Code) | | When an operation results in a change in the smallest key in a block,
it is necessary to inform the parent block of the change, since the
parent block key for this block is required to be the key of the
smallest item in this block.
Parameters:
b - the block containing the new lowest key
Parameters:
prevLow - the key which was previously the lowest key. true if block b is now empty, and has beenfreed and unlinked from the tree. Don't touch this blockany more! |
| propogateSplit | | final void propogateSplit(Block[] ba) throws IOException(Code) | | After the split operation, propagate information up the tree to
the parent block about the newly created block and the new key
distribution.
Parameters:
ba - a two-element array, with ba[0] beingthe pre-split block, and ba[1] the new block |
| set | | final public boolean set(byte[] key, int klen, byte[] data, int doff, int dlen, boolean insOk, boolean updOk) throws IOException(Code) | | Implement the set operation.
Parameters:
key - the key
Parameters:
data - the data |
| set | | final boolean set(Block b, byte[] key, int klen, byte[] data, int doff, int dlen, boolean insOk, boolean updOk) throws IOException(Code) | | Recursive implementation of set(key, data).
Precondition: The caller must already have a write-lock on
b.
Parameters:
b - the block to be searched
Parameters:
key - the search key
Parameters:
data - the data associated with the key true if the key already existed before the set, false otherwise. |
| setBos | | final public static void setBos(Block b, int bos)(Code) | | Set the value of the bos field.
|
| setCount | | final public static void setCount(Block b, int count)(Code) | | Set the value of the count field.
|
| setFlag | | final public static void setFlag(Block b, int mask, boolean val)(Code) | | Set a specified boolean flag.
|
| setFlags | | final public static void setFlags(Block b, int flags)(Code) | | Set the value of the flags field.
|
| setGarbage | | final public static void setGarbage(Block b, int g)(Code) | | Set the value of the garbage field.
|
| setKey | | final Block setKey(Block b, int index, byte[] key, int klen, byte[] data, int doff, int dlen, boolean replace) throws IOException(Code) | | Insert or replace a key in the specified block, which may or may
not be a leaf block. Handle split operations: if a split is required,
determine which post-split block this key should be added to.
Also, if the new key happens to be key zero (i.e., the lowest valued
key in this block), then adjust the parent's reference to this block
accordingly. Although, maybe that can't happen?
PRECONDITION: Lock/ref on block b
POSTCONDITION: Lock/ref on block b
the block into which the key was actually stored. Thiswill be different from b if a split wasnecessary. |
| setKeyAtPos | | final boolean setKeyAtPos(Block b, int index, byte[] key, int klen, byte[] data, int doff, int dlen, boolean replace) throws IOException(Code) | | Given a block and a key position, insert a new key/data pair
immediately at the specified position, returning true if the
key/data fit in the block. If the incoming data won't fit,
don't modify the block and return false.
Parameters:
b - the block to be modified.
Parameters:
index - the position in the key array
Parameters:
key - the key
Parameters:
data - the data true if the insert was performed successfully, falseif not because of, e.g., "wont fit". |
| setKeyIndex | | final static void setKeyIndex(Block b, int index, int val)(Code) | | Set the byte offset for the specified key/data pair.
Parameters:
b - the Bnode containing the key
Parameters:
index - the index of the specified key/data pair.
Parameters:
val - the byte offset of the specified key/data pair. |
| setLeaf | | final public static void setLeaf(Block b, boolean v)(Code) | | Set the value of the IS_LEAF flag.
|
| setParent | | final public static void setParent(Block b, long g)(Code) | | Set the value of the parent field.
|
| size | | public int size() throws IOException(Code) | | Return the number of keys in this subtree. This implicitly only
counts entries in the leaf nodes.
|
| split | | final void split(Block[] ba) throws IOException(Code) | | Split this block, by creaing a new block and moving half of this
block's keys into the new block. Then, add a new key to the parent
block to reflect the new block, and adjust the parent's old reference
to this block to reflect the new key distribution.
PRECONDITION: We have a ref/lock on ba[0]
POSTCONDITION: We have a ref on ba[1]
Parameters:
ba - a two-element array, with ba[0] beingthe pre-split block, and ba[1] the new block |
| splitHelp | | final void splitHelp(Block[] ba, long nbno) throws IOException(Code) | | Split helper:
PRECONDITION: Ref/lock on both ba[0], ba[1]
|
| totalLength | | final static int totalLength(int len)(Code) | | Compute the total number of bytes that will be required to store
the byte array 'b' plus its length code.
Parameters:
b - the byte array the length of the byte array plus the length of the lengthcode. |
| writeLenLen | | final static int writeLenLen(Block b, int bos, int len)(Code) | | Write a length code for the specified length, working backwards in
the data area, and returning the new bottom of the data area.
|
|
|