com.sleepycat.je.tree
Class Tree

java.lang.Object
  extended by com.sleepycat.je.tree.Tree
All Implemented Interfaces:
LogReadable, LogWritable

public final class Tree
extends Object
implements LogWritable, LogReadable

Tree implements the JE B+Tree. A note on tree search patterns: There's a set of Tree.search* methods. Some clients of the tree use those search methods directly, whereas other clients of the tree tend to use methods built on top of search. The semantics of search* are they leave you pointing at a BIN or IN they don't tell you where the reference of interest is. they traverse a single tree, to jump into the duplicate tree, the caller has to take explicit action. The semantics of the get* methods are: they leave you pointing at a BIN or IN they return the index of the slot of interest they traverse down to whatever level is needed -- they'll take care of jumping into the duplicate tree. they are built on top of search* methods. For the future: Over time, we need to clarify which methods are to be used by clients of the tree. Preferably clients that call the tree use get*, although their are cases where they need visibility into the tree structure. For example, tee cursors use search* because they want to add themselves to BIN before jumping into the duplicate tree. Also, search* should return the location of the slot to save us a second binary search.


Nested Class Summary
static class Tree.SearchType
          Embodies an enum for the type of search being performed.
 
Constructor Summary
Tree()
          Create a tree that's being read in from the log.
Tree(DatabaseImpl database)
          Create a new tree.
 
Method Summary
 boolean delete(byte[] idKey, UtilizationTracker tracker)
          Deletes a BIN specified by key from the tree.
 boolean deleteDup(byte[] idKey, byte[] dupKey, UtilizationTracker tracker)
          Delete a subtree of a duplicate tree.
 void dump()
           
 void dumpLog(StringBuffer sb, boolean verbose)
          Write the object into the string buffer for log dumping.
 String dumpString(int nSpaces)
           
 DatabaseImpl getDatabase()
           
 IN getFirstNode()
          Find the leftmost node (IN or BIN) in the tree.
 DBIN getFirstNode(DIN duplicateRoot)
          Find the leftmost node (DBIN) in a duplicate tree.
 IN getLastNode()
          Find the rightmost node (IN or BIN) in the tree.
 DBIN getLastNode(DIN duplicateRoot)
          Find the rightmost node (DBIN) in a duplicate tree.
 int getLogSize()
           
 BIN getNextBin(BIN bin, DIN duplicateRoot)
          Return a reference to the next BIN in a duplicate tree.
 boolean getParentBINForChildLN(TreeLocation location, byte[] mainKey, byte[] dupKey, LN ln, boolean splitsAllowed, boolean findDeletedEntries, boolean searchDupTree, boolean updateGeneration)
          Return a reference to the parent of this LN.
 SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, boolean updateGeneration)
          GetParentNode without optional tracking.
 SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, boolean updateGeneration, int targetLevel, List trackingList)
          Return a reference to the parent or possible parent of the child.
 SearchResult getParentINForChildIN(long targetNodeId, boolean targetContainsDuplicates, boolean targetIsRoot, byte[] targetMainTreeKey, byte[] targetDupTreeKey, boolean requireExactMatch, boolean updateGeneration, int targetLevel, List trackingList, boolean doFetch)
          Return a reference to the parent or possible parent of the child.
 BIN getPrevBin(BIN bin, DIN duplicateRoot)
          Return a reference to the previous BIN in a duplicate tree.
 long getTransactionId()
           
(package private)  TreeStats getTreeStats()
           
 boolean insert(LN ln, byte[] key, boolean allowDuplicates, CursorImpl cursor, LockResult lnLock)
          Inserts a new LN into the tree.
 boolean logEntryIsTransactional()
           
 void readFromLog(ByteBuffer itemBuffer, byte entryTypeVersion)
          Initialize this object from the data in itemBuf.
 void rebuildINList()
          rebuildINList is used by recovery to add all the resident nodes to the IN list.
 IN search(byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, boolean updateGeneration)
          Search the tree, starting at the root.
 IN searchSplitsAllowed(byte[] key, long nid, boolean updateGeneration)
          Do a key based search, permitting pre-emptive splits.
 IN searchSubTree(IN parent, byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, boolean updateGeneration)
          Searches a portion of the tree starting at parent using key.
 void setDatabase(DatabaseImpl database)
          Set the database for this tree.
 void setRoot(ChildReference newRoot)
          Set the root for the tree.
 void setSearchHook(TestHook hook)
           
 void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)
           
 void setWaitHook(TestHook hook)
           
(package private)  boolean validateDelete(int index)
          Unit test support to validate subtree pruning.
 void validateINList(IN parent)
          Debugging check that all resident nodes are on the INList and no stray nodes are present in the unused portion of the IN arrays.
 IN withRootLatched(WithRootLatched wrl)
           
 void writeToLog(ByteBuffer logBuffer)
          Serialize this object into the buffer.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Tree

public Tree(DatabaseImpl database)
     throws DatabaseException
Create a new tree.

Throws:
DatabaseException

Tree

public Tree()
Create a tree that's being read in from the log.

Method Detail

setDatabase

public void setDatabase(DatabaseImpl database)
                 throws DatabaseException
Set the database for this tree. Used by recovery when recreating an existing tree.

Throws:
DatabaseException

getDatabase

public DatabaseImpl getDatabase()
Returns:
the database for this Tree.

setRoot

public void setRoot(ChildReference newRoot)
Set the root for the tree. Should only be called within the root latch.


getTreeStats

TreeStats getTreeStats()
Returns:
the TreeStats for this tree.

setTreeStatsAccumulator

public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)

withRootLatched

public IN withRootLatched(WithRootLatched wrl)
                   throws DatabaseException
Throws:
DatabaseException

delete

public boolean delete(byte[] idKey,
                      UtilizationTracker tracker)
               throws DatabaseException
Deletes a BIN specified by key from the tree. The reference from the node's parent is removed. If removing that reference leaves no more entries in that IN, that IN is removed, and so on up the tree. We don't try to delete a BIN if there are cursors referring to it. Upon exiting this routine, the node is removed from the tree and is unlatched, unless search found that the BIN has entries in it (perhaps because someone came along and added entries between the time the BIN was put on the Compressor queue and the time the Compressor got around to compressing.) Assumes the INList major latch is held.

Parameters:
idKey - - the identifier key of the node to delete.
tracker - is used for tracking obsolete node info.
Returns:
true if the item deleted was the root of the tree, false otherwise.
Throws:
DatabaseException

deleteDup

public boolean deleteDup(byte[] idKey,
                         byte[] dupKey,
                         UtilizationTracker tracker)
                  throws DatabaseException
Delete a subtree of a duplicate tree. Find the duplicate tree using dupKey in the top part of the tree and idKey in the duplicate tree. In the duplicate tree do a SearchType.DELETE to find the largest subtree that can be deleted safely. Assumes the INList major latch is held.

Parameters:
idKey - the identifier key to be used in the duplicate subtree to find the duplicate path.
dupKey - the duplicate key to be used in the main tree to find the duplicate subtree.
tracker - is used for tracking obsolete node info.
Returns:
true if the delete succeeded, false if there were still cursors present on the leaf DBIN of the subtree that was located.
Throws:
DatabaseException

getFirstNode

public IN getFirstNode()
                throws DatabaseException
Find the leftmost node (IN or BIN) in the tree. Do not descend into a duplicate tree if the leftmost entry of the first BIN refers to one.

Returns:
the leftmost node in the tree, null if the tree is empty. The returned node is latched and the caller must release it.
Throws:
DatabaseException

getLastNode

public IN getLastNode()
               throws DatabaseException
Find the rightmost node (IN or BIN) in the tree. Do not descend into a duplicate tree if the rightmost entry of the last BIN refers to one.

Returns:
the rightmost node in the tree, null if the tree is empty. The returned node is latched and the caller must release it.
Throws:
DatabaseException

getFirstNode

public DBIN getFirstNode(DIN duplicateRoot)
                  throws DatabaseException
Find the leftmost node (DBIN) in a duplicate tree.

Returns:
the leftmost node in the tree, null if the tree is empty. The returned node is latched and the caller must release it.
Throws:
DatabaseException

getLastNode

public DBIN getLastNode(DIN duplicateRoot)
                 throws DatabaseException
Find the rightmost node (DBIN) in a duplicate tree.

Returns:
the rightmost node in the tree, null if the tree is empty. The returned node is latched and the caller must release it.
Throws:
DatabaseException

getParentINForChildIN

public SearchResult getParentINForChildIN(IN child,
                                          boolean requireExactMatch,
                                          boolean updateGeneration)
                                   throws DatabaseException
GetParentNode without optional tracking.

Throws:
DatabaseException

getParentINForChildIN

public SearchResult getParentINForChildIN(IN child,
                                          boolean requireExactMatch,
                                          boolean updateGeneration,
                                          int targetLevel,
                                          List trackingList)
                                   throws DatabaseException
Return a reference to the parent or possible parent of the child. Used by objects that need to take a standalone node and find it in the tree, like the evictor, checkpointer, and recovery.

Parameters:
child - The child node for which to find the parent. This node is latched by the caller and is released by this function before returning to the caller.
requireExactMatch - if true, we must find the exact parent, not a potential parent.
updateGeneration - if true, set the generation count during latching. Pass false when the LRU should not be impacted, such as during eviction and checkpointing.
trackingList - if not null, add the LSNs of the parents visited along the way, as a debug tracing mechanism. This is meant to stay in production, to add information to the log.
Returns:
a SearchResult object. If the parent has been found, result.foundExactMatch is true. If any parent, exact or potential has been found, result.parent refers to that node.
Throws:
DatabaseException

getParentINForChildIN

public SearchResult getParentINForChildIN(long targetNodeId,
                                          boolean targetContainsDuplicates,
                                          boolean targetIsRoot,
                                          byte[] targetMainTreeKey,
                                          byte[] targetDupTreeKey,
                                          boolean requireExactMatch,
                                          boolean updateGeneration,
                                          int targetLevel,
                                          List trackingList,
                                          boolean doFetch)
                                   throws DatabaseException
Return a reference to the parent or possible parent of the child. Used by objects that need to take a node id and find it in the tree, like the evictor, checkpointer, and recovery.

Parameters:
requireExactMatch - if true, we must find the exact parent, not a potential parent.
updateGeneration - if true, set the generation count during latching. Pass false when the LRU should not be impacted, such as during eviction and checkpointing.
trackingList - if not null, add the LSNs of the parents visited along the way, as a debug tracing mechanism. This is meant to stay in production, to add information to the log.
doFetch - if false, stop the search if we run into a non-resident child. Used by the checkpointer to avoid conflicting with work done by the evictor.
child - The child node for which to find the parent. This node is latched by the caller and is released by this function before returning to the caller.
Returns:
a SearchResult object. If the parent has been found, result.foundExactMatch is true. If any parent, exact or potential has been found, result.parent refers to that node.
Throws:
DatabaseException

getParentBINForChildLN

public boolean getParentBINForChildLN(TreeLocation location,
                                      byte[] mainKey,
                                      byte[] dupKey,
                                      LN ln,
                                      boolean splitsAllowed,
                                      boolean findDeletedEntries,
                                      boolean searchDupTree,
                                      boolean updateGeneration)
                               throws DatabaseException
Return a reference to the parent of this LN. This searches through the main and duplicate tree and allows splits. Set the tree location to the proper BIN parent whether or not the LN child is found. That's because if the LN is not found, recovery or abort will need to place it within the tree, and so we must point at the appropriate position.

When this method returns with location.bin non-null, the BIN is latched and must be unlatched by the caller. Note that location.bin may be non-null even if this method returns false.

Parameters:
location - a holder class to hold state about the location of our search. Sort of an internal cursor.
mainKey - key to navigate through main key
dupKey - key to navigate through duplicate tree. May be null, since deleted lns have no data.
ln - the node instantiated from the log
splitsAllowed - true if this method is allowed to cause tree splits as a side effect. In practice, recovery can cause splits, but abort can't.
searchDupTree - true if a search through the dup tree looking for a match on the ln's node id should be made (only in the case where dupKey == null). See SR 8984.
updateGeneration - if true, set the generation count during latching. Pass false when the LRU should not be impacted, such as during eviction and checkpointing.
Returns:
true if node found in tree. If false is returned and there is the possibility that we can insert the record into a plausible parent we must also set - location.bin (may be null if no possible parent found) - location.lnKey (don't need to set if no possible parent).
Throws:
DatabaseException

getNextBin

public BIN getNextBin(BIN bin,
                      DIN duplicateRoot)
               throws DatabaseException
Return a reference to the next BIN in a duplicate tree.

Parameters:
child - The BIN to find the next BIN for. The BIN is latched.
duplicateRoot - The root of the duplicate tree that is being iterated through or null if the root of the tree should be used. It should not be latched (if non-null) when this is called.
Returns:
The next BIN, or null if there are no more. The returned node is latched and the caller must release it. If null is returned, the argument BIN remains latched.
Throws:
DatabaseException

getPrevBin

public BIN getPrevBin(BIN bin,
                      DIN duplicateRoot)
               throws DatabaseException
Return a reference to the previous BIN in a duplicate tree.

Parameters:
child - The BIN to find the previous BIN for. The BIN is latched.
duplicateRoot - The root of the duplicate tree that is being iterated through or null if the root of the tree should be used. It should not be latched (if non-null) when this is called.
Returns:
The previous BIN, or null if there are no more. The returned node is latched and the caller must release it. If null is returned, the argument bin remains latched.
Throws:
DatabaseException

search

public IN search(byte[] key,
                 Tree.SearchType searchType,
                 long nid,
                 BINBoundary binBoundary,
                 boolean updateGeneration)
          throws DatabaseException
Search the tree, starting at the root. Depending on search type either search using key, or search all the way down the right or left sides. Stop the search either when the bottom of the tree is reached, or a node matching nid is found (see below) in which case that node's parent is returned. Preemptive splitting is not done during the search.

Parameters:
key - - the key to search for, or null if searchType is LEFT or RIGHT.
searchType - - The type of tree search to perform. NORMAL means we're searching for key in the tree. LEFT/RIGHT means we're descending down the left or right side, resp. DELETE means we're descending the tree and will return the lowest node in the path that has > 1 entries.
nid - - The nodeid to search for in the tree. If found, returns its parent. If the nodeid of the root is passed, null is returned.
binBoundary - - If non-null, information is returned about whether the BIN found is the first or last BIN in the database.
Returns:
- the Node that matches the criteria, if any. This is the node that is farthest down the tree with a match. Returns null if the root is null. Node is latched (unless it's null) and must be unlatched by the caller. Only IN's and BIN's are returned, not LN's. In a NORMAL search, It is the caller's responsibility to do the findEntry() call on the key and BIN to locate the entry that matches key. The return value node is latched upon return and it is the caller's responsibility to unlatch it.
Throws:
DatabaseException

searchSplitsAllowed

public IN searchSplitsAllowed(byte[] key,
                              long nid,
                              boolean updateGeneration)
                       throws DatabaseException
Do a key based search, permitting pre-emptive splits. Returns the target node's parent.

Throws:
DatabaseException

searchSubTree

public IN searchSubTree(IN parent,
                        byte[] key,
                        Tree.SearchType searchType,
                        long nid,
                        BINBoundary binBoundary,
                        boolean updateGeneration)
                 throws DatabaseException
Searches a portion of the tree starting at parent using key. If during the search a node matching a non-null nid argument is found, its parent is returned. If searchType is NORMAL, then key must be supplied to guide the search. If searchType is LEFT (or RIGHT), then the tree is searched down the left (or right) side to find the first (or last) leaf, respectively. DELETE means we're descending the tree and will return the lowest node in the path that has > 1 entries.

In the DELETE case, we verify that the BIN at the bottom of the subtree has no entries in it because compression is about to occur. If there are entries in it (because entries were added between the time that the BIN was turned into an empty BIN and the time that the compressor got around to compressing it) then we unlatch everything before returning and throw a NodeNotEmptyException.

Enters with parent latched, assuming it's not null. Exits with the return value latched, assuming it's not null.

Parameters:
parent - - the root of the subtree to start the search at. This node should be latched by the caller and will be unlatched prior to return.
key - - the key to search for, unless searchType is LEFT or RIGHT
searchType - - NORMAL means search using key and, optionally, nid. LEFT means find the first (leftmost) leaf RIGHT means find the last (rightmost) leaf DELETE means find the lowest node with > 1 entries.
nid - - The nodeid to search for in the tree. If found, returns its parent. If the nodeid of the root is passed, null is returned. Pass -1 if no nodeid based search is desired.
Returns:
- the node matching the argument criteria, or null. The node is latched and must be unlatched by the caller. The parent argument and any other nodes that are latched during the search are unlatched prior to return.
Throws:
NodeNotEmptyException - if DELETE was passed as a parameter and the lowest level BIN at the bottom of the tree was not empty.
DatabaseException

insert

public boolean insert(LN ln,
                      byte[] key,
                      boolean allowDuplicates,
                      CursorImpl cursor,
                      LockResult lnLock)
               throws DatabaseException
Inserts a new LN into the tree.

Parameters:
ln - The LN to insert into the tree.
key - Key value for the node
allowDuplicates - whether to allow duplicates to be inserted
cursor - the cursor to update to point to the newly inserted key/data pair, or null if no cursor should be updated.
Returns:
true if LN was inserted, false if it was a duplicate duplicate or if an attempt was made to insert a duplicate when allowDuplicates was false.
Throws:
DatabaseException

getLogSize

public int getLogSize()
Specified by:
getLogSize in interface LogWritable
Returns:
number of bytes used to store this object.
See Also:
LogWritable.getLogSize()

writeToLog

public void writeToLog(ByteBuffer logBuffer)
Description copied from interface: LogWritable
Serialize this object into the buffer.

Specified by:
writeToLog in interface LogWritable
Parameters:
logBuffer - is the destination buffer
See Also:
LogWritable.writeToLog(java.nio.ByteBuffer)

readFromLog

public void readFromLog(ByteBuffer itemBuffer,
                        byte entryTypeVersion)
Description copied from interface: LogReadable
Initialize this object from the data in itemBuf.

Specified by:
readFromLog in interface LogReadable
See Also:
LogReadable.readFromLog(java.nio.ByteBuffer, byte)

dumpLog

public void dumpLog(StringBuffer sb,
                    boolean verbose)
Description copied from interface: LogReadable
Write the object into the string buffer for log dumping. Each object should be dumped without indentation or new lines and should be valid XML.

Specified by:
dumpLog in interface LogReadable
Parameters:
sb - destination string buffer
verbose - if true, dump the full, verbose version
See Also:
LogReadable.dumpLog(java.lang.StringBuffer, boolean)

logEntryIsTransactional

public boolean logEntryIsTransactional()
Specified by:
logEntryIsTransactional in interface LogReadable
Returns:
true if the LogEntry is a transactional log entry type.
See Also:
LogReadable#isTransactional

getTransactionId

public long getTransactionId()
Specified by:
getTransactionId in interface LogReadable
Returns:
return the transaction id if this log entry is transactional, 0 otherwise.
See Also:
LogReadable.getTransactionId()

rebuildINList

public void rebuildINList()
                   throws DatabaseException
rebuildINList is used by recovery to add all the resident nodes to the IN list.

Throws:
DatabaseException

dump

public void dump()
          throws DatabaseException
Throws:
DatabaseException

dumpString

public String dumpString(int nSpaces)
                  throws DatabaseException
Throws:
DatabaseException

validateDelete

boolean validateDelete(int index)
                 throws DatabaseException
Unit test support to validate subtree pruning. Didn't want to make root access public.

Throws:
DatabaseException

validateINList

public void validateINList(IN parent)
                    throws DatabaseException
Debugging check that all resident nodes are on the INList and no stray nodes are present in the unused portion of the IN arrays.

Throws:
DatabaseException

setWaitHook

public void setWaitHook(TestHook hook)

setSearchHook

public void setSearchHook(TestHook hook)


Copyright 2004-2005 Sleepycat, Inc. All Rights Reserved.