com.sleepycat.je.tree
Class Tree

java.lang.Object
  extended by com.sleepycat.je.tree.Tree
All Implemented Interfaces:
Loggable

public final class Tree
extends java.lang.Object
implements Loggable

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
 void delete(byte[] idKey, LocalUtilizationTracker localTracker)
          Deletes a BIN specified by key from the tree.
 void deleteDup(byte[] idKey, byte[] mainKey, LocalUtilizationTracker localTracker)
          Delete a subtree of a duplicate tree.
 void dump()
           
 void dumpLog(java.lang.StringBuffer sb, boolean verbose)
          Write the object into the string buffer for log dumping.
 java.lang.String dumpString(int nSpaces)
           
 DatabaseImpl getDatabase()
           
 IN getFirstNode(CacheMode cacheMode)
          Find the leftmost node (IN or BIN) in the tree.
 DBIN getFirstNode(DIN dupRoot, CacheMode cacheMode)
          Find the leftmost node (DBIN) in a duplicate tree.
 IN getLastNode(CacheMode cacheMode)
          Find the rightmost node (IN or BIN) in the tree.
 DBIN getLastNode(DIN dupRoot, CacheMode cacheMode)
          Find the rightmost node (DBIN) in a duplicate tree.
 int getLogSize()
           
 BIN getNextBin(BIN bin, boolean traverseWithinDupTree, CacheMode cacheMode)
          Return a reference to the adjacent BIN.
 boolean getParentBINForChildLN(TreeLocation location, byte[] mainKey, byte[] dupKey, LN ln, boolean splitsAllowed, boolean findDeletedEntries, boolean searchDupTree, CacheMode cacheMode)
          Return a reference to the parent of this LN.
 SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, CacheMode cacheMode)
          GetParentNode without optional tracking.
 SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, CacheMode cacheMode, int targetLevel, java.util.List<TrackingInfo> 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, CacheMode cacheMode, int targetLevel, java.util.List<TrackingInfo> trackingList, boolean doFetch)
          Return a reference to the parent or possible parent of the child.
 BIN getPrevBin(BIN bin, boolean traverseWithinDupTree, CacheMode cacheMode)
          Return a reference to the previous BIN.
 IN getResidentRootIN(boolean latched)
           
 IN getRootIN(CacheMode cacheMode)
          Helper to obtain the root IN with shared root latching.
 IN getRootINLatchedExclusive(CacheMode cacheMode)
          Helper to obtain the root IN with exclusive root latching.
 long getRootLsn()
          Get LSN of the rootIN.
 long getTransactionId()
           
 boolean insert(LN ln, byte[] key, boolean allowDuplicates, CursorImpl cursor, LockResult lnLock, ReplicationContext repContext)
          Inserts a new LN into the tree.
 boolean isRootResident()
          Perform a fast check to see if the root IN is resident.
 boolean logicalEquals(Loggable other)
           
 ChildReference makeRootChildReference(Node target, byte[] key, long lsn)
           
 void readFromLog(java.nio.ByteBuffer itemBuffer, byte entryVersion)
          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.
 boolean rootExists()
           
 IN search(byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, CacheMode cacheMode)
          Search the tree, starting at the root.
 void searchDeletableSubTree(IN parent, byte[] key, java.util.ArrayList<com.sleepycat.je.tree.Tree.SplitInfo> nodeLadder)
          Search down the tree using a key, but instead of returning the BIN that houses that key, find the point where we can detach a deletable subtree.
 IN searchSplitsAllowed(byte[] key, long nid, CacheMode cacheMode)
          Do a key based search, permitting pre-emptive splits.
 IN searchSubTree(IN parent, byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, CacheMode cacheMode)
          Wrapper for searchSubTreeInternal that does a restart if a RelatchRequiredException is thrown (i.e.
 void setCkptHook(TestHook hook)
           
 void setDatabase(DatabaseImpl database)
          Set the database for this tree.
 void setRoot(ChildReference newRoot, boolean notLatched)
          Set the root for the tree.
 void setSearchHook(TestHook hook)
           
 void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)
           
 void setWaitHook(TestHook hook)
           
 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 withRootLatchedExclusive(WithRootLatched wrl)
           
 IN withRootLatchedShared(WithRootLatched wrl)
           
 void writeToLog(java.nio.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()
     throws DatabaseException
Create a tree that's being read in from the log.

Throws:
DatabaseException
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,
                    boolean notLatched)
Set the root for the tree. Should only be called within the root latch.


makeRootChildReference

public ChildReference makeRootChildReference(Node target,
                                             byte[] key,
                                             long lsn)

rootExists

public boolean rootExists()

isRootResident

public boolean isRootResident()
Perform a fast check to see if the root IN is resident. No latching is performed. To ensure that the root IN is not loaded by another thread, this method should be called while holding a write lock on the MapLN. That will prevent opening the DB in another thread, and potentially loading the root IN. [#13415]


getRootLsn

public long getRootLsn()
Get LSN of the rootIN. Obtained without latching, should only be accessed while quiescent.


setTreeStatsAccumulator

public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)

withRootLatchedExclusive

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

withRootLatchedShared

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

delete

public void delete(byte[] idKey,
                   LocalUtilizationTracker localTracker)
            throws DatabaseException,
                   NodeNotEmptyException,
                   CursorsExistException
Deletes a BIN specified by key from the tree. If the BIN resides in a subtree that can be pruned away, prune as much as possible, so we don't leave a branch that has no BINs. It's possible that the targeted BIN will now have entries, or will have resident cursors. Either will prevent deletion.

Parameters:
idKey - - the identifier key of the node to delete.
localTracker - is used for tracking obsolete node info.
Throws:
DatabaseException
NodeNotEmptyException
CursorsExistException

deleteDup

public void deleteDup(byte[] idKey,
                      byte[] mainKey,
                      LocalUtilizationTracker localTracker)
               throws DatabaseException,
                      NodeNotEmptyException,
                      CursorsExistException
Delete a subtree of a duplicate tree. Find the duplicate tree using mainKey in the top part of the tree and idKey in the duplicate tree.

Parameters:
idKey - the identifier key to be used in the duplicate subtree to find the duplicate path.
mainKey - the key to be used in the main tree to find the duplicate subtree.
localTracker - is used for tracking obsolete node info.
Throws:
DatabaseException
NodeNotEmptyException
CursorsExistException

getFirstNode

public IN getFirstNode(CacheMode cacheMode)
                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(CacheMode cacheMode)
               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 dupRoot,
                         CacheMode cacheMode)
                  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 dupRoot,
                        CacheMode cacheMode)
                 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,
                                          CacheMode cacheMode)
                                   throws DatabaseException
GetParentNode without optional tracking.

Throws:
DatabaseException

getParentINForChildIN

public SearchResult getParentINForChildIN(IN child,
                                          boolean requireExactMatch,
                                          CacheMode cacheMode,
                                          int targetLevel,
                                          java.util.List<TrackingInfo> 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.
cacheMode - The CacheMode for affecting the hotness of the tree.
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,
                                          CacheMode cacheMode,
                                          int targetLevel,
                                          java.util.List<TrackingInfo> 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.
cacheMode - The CacheMode for affecting the hotness of the tree.
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.
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,
                                      CacheMode cacheMode)
                               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.
cacheMode - The CacheMode for affecting the hotness of the tree.
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,
                      boolean traverseWithinDupTree,
                      CacheMode cacheMode)
               throws DatabaseException
Return a reference to the adjacent BIN.

Parameters:
bin - The BIN to find the next BIN for. This BIN is latched.
traverseWithinDupTree - if true, only search within the dup tree and return null when the traversal runs out of duplicates.
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,
                      boolean traverseWithinDupTree,
                      CacheMode cacheMode)
               throws DatabaseException
Return a reference to the previous BIN.

Parameters:
bin - The BIN to find the next BIN for. This BIN is latched.
traverseWithinDupTree - if true, only search within the dup tree and return null when the traversal runs out of duplicates.
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,
                 CacheMode cacheMode)
          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,
                              CacheMode cacheMode)
                       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,
                        CacheMode cacheMode)
                 throws DatabaseException
Wrapper for searchSubTreeInternal that does a restart if a RelatchRequiredException is thrown (i.e. a relatch of the root is needed.

Throws:
DatabaseException

searchDeletableSubTree

public void searchDeletableSubTree(IN parent,
                                   byte[] key,
                                   java.util.ArrayList<com.sleepycat.je.tree.Tree.SplitInfo> nodeLadder)
                            throws DatabaseException,
                                   NodeNotEmptyException,
                                   CursorsExistException
Search down the tree using a key, but instead of returning the BIN that houses that key, find the point where we can detach a deletable subtree. A deletable subtree is a branch where each IN has one child, and the bottom BIN has no entries and no resident cursors. That point can be found by saving a pointer to the lowest node in the path with more than one entry. INa / \ INb INc | | INd .. / \ INe .. | BINx (suspected of being empty) In this case, we'd like to prune off the subtree headed by INe. INd is the parent of this deletable subtree. As we descend, we must keep latches for all the nodes that will be logged. In this case, we will need to keep INa, INb and INd latched when we return from this method. The method returns a list of parent/child/index structures. In this example, the list will hold: INa/INb/index INb/INd/index INd/INe/index Every node is latched, and every node except for the bottom most child (INe) must be logged.

Throws:
DatabaseException
NodeNotEmptyException
CursorsExistException

getRootIN

public IN getRootIN(CacheMode cacheMode)
             throws DatabaseException
Helper to obtain the root IN with shared root latching. Optionally updates the generation of the root when latching it.

Throws:
DatabaseException

getRootINLatchedExclusive

public IN getRootINLatchedExclusive(CacheMode cacheMode)
                             throws DatabaseException
Helper to obtain the root IN with exclusive root latching. Optionally updates the generation of the root when latching it.

Throws:
DatabaseException

getResidentRootIN

public IN getResidentRootIN(boolean latched)
                     throws DatabaseException
Throws:
DatabaseException

insert

public boolean insert(LN ln,
                      byte[] key,
                      boolean allowDuplicates,
                      CursorImpl cursor,
                      LockResult lnLock,
                      ReplicationContext repContext)
               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 Loggable
Returns:
number of bytes used to store this object.
See Also:
Loggable.getLogSize()

writeToLog

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

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

readFromLog

public void readFromLog(java.nio.ByteBuffer itemBuffer,
                        byte entryVersion)
Description copied from interface: Loggable
Initialize this object from the data in itemBuf.

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

dumpLog

public void dumpLog(java.lang.StringBuffer sb,
                    boolean verbose)
Description copied from interface: Loggable
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 Loggable
Parameters:
sb - destination string buffer
verbose - if true, dump the full, verbose version
See Also:
Loggable.dumpLog(java.lang.StringBuffer, boolean)

getTransactionId

public long getTransactionId()
Specified by:
getTransactionId in interface Loggable
Returns:
the transaction id embedded within this loggable object. Objects that have no transaction id should return 0.
See Also:
Loggable.getTransactionId()

logicalEquals

public boolean logicalEquals(Loggable other)
Specified by:
logicalEquals in interface Loggable
Returns:
true if these two loggable items are logically the same. Used for replication testing.
See Also:
Always return false, this item should never be compared.

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 java.lang.String dumpString(int nSpaces)
                            throws DatabaseException
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)

setCkptHook

public void setCkptHook(TestHook hook)