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 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. 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 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. Also, search* should return the location of the slot to save us a second binary search. Search Method Call Hierarchy ---------------------------- getFirst/LastNode search CALLED BY: CursorImpl.getFirstOrLast getNext/PrevBin getParentINForChildIN searchSubTree CALLED BY: DupConvert CursorImpl.getNext getParentINForChildIN IN.findParent does not use shared latching CALLED BY: Checkpointer.flushIN (doFetch=false, targetLevel=-1) FileProcessor.processIN (doFetch=true, targetLevel=LEVEL) Evictor.evictIN (doFetch=true, targetLevel=-1) RecoveryManager.replaceOrInsertChild (doFetch=true, targetLevel=-1) getNext/PrevBin (doFetch=true, targetLevel=-1) search searchSubTree CALLED BY: CursorImpl.searchAndPosition INCompressor to find BIN searchSubTree uses shared grandparent latching getParentBINForChildLN searchSplitsAllowed CALLED BY: RecoveryManager.redo RecoveryManager.recoveryUndo search CALLED BY: RecoveryManager.abortUndo RecoveryManager.rollbackUndo FileProcessor.processLN Cleaner.processPendingLN UtilizationProfile.verifyLsnIsObsolete (utility) findBinForInsert searchSplitsAllowed CALLED BY: CursorImpl.putInternal searchSplitsAllowed uses shared non-grandparent latching CALLED BY: DupConvert (instead of findBinForInsert, which needs a cursor) Possible Shared Latching Improvements ------------------------------------- By implementing grandparent latching in searchSplitsAllowed we would increase performance slightly in these cases: Insertions By implementing shared latching in getParentINForChildIN we would get better concurrency in these cases: Cursor scan, when moving between BINs Eviction Checkpoints Cleaning INs By implementing shared latching for BINs we would get better concurrency in these cases: Reads when LN is in cache, or LN is not needed (key-only op, e.g., dups)


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 dump()
           
 void dumpLog(StringBuilder sb, boolean verbose)
          Write the object into the string buffer for log dumping.
 String dumpString(int nSpaces)
           
 void findBinForInsert(byte[] key, CursorImpl cursor)
          Find the BIN that is relevant to the insert.
 DatabaseImpl getDatabase()
           
 IN getFirstNode(CacheMode cacheMode)
          Find the leftmost node (IN or BIN) in the tree.
 IN getLastNode(CacheMode cacheMode)
          Find the rightmost node (IN or BIN) in the tree.
 int getLogSize()
           
 long getMaxLNs()
          Cheaply calculates and returns the maximum possible number of LNs in the btree.
 BIN getNextBin(BIN bin, CacheMode cacheMode)
          Return a reference to the adjacent BIN.
 boolean getParentBINForChildLN(TreeLocation location, byte[] key, boolean splitsAllowed, boolean findDeletedEntries, 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, List<TrackingInfo> trackingList)
          Return a reference to the parent or possible parent of the child.
 SearchResult getParentINForChildIN(long targetNodeId, boolean targetIsRoot, byte[] targetTreeKey, boolean requireExactMatch, CacheMode cacheMode, int targetLevel, List<TrackingInfo> trackingList, boolean doFetch)
          Return a reference to the parent or possible parent of the child.
 BIN getPrevBin(BIN bin, 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()
           
(package private)  int getTreeStats()
           
 boolean isRootResident()
          Perform a fast check to see if the root IN is resident.
 void latchRootLatchExclusive()
           
 void loadStats(StatsConfig config, BtreeStats btreeStats)
           
 boolean logicalEquals(Loggable other)
           
 ChildReference makeRootChildReference(Node target, byte[] key, long lsn)
           
 void readFromLog(ByteBuffer itemBuffer, int 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.
 void releaseRootLatch()
           
 boolean rootExists()
           
 IN search(byte[] key, Tree.SearchType searchType, BINBoundary binBoundary, CacheMode cacheMode, Comparator<byte[]> searchComparator)
          Search the tree, starting at the root.
 void searchDeletableSubTree(IN parent, byte[] key, 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, CacheMode cacheMode, Comparator<byte[]> searchComparator)
          Do a key based search, permitting pre-emptive splits.
 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)
           
(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 withRootLatchedExclusive(WithRootLatched wrl)
           
 IN withRootLatchedShared(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)
Create a new tree.


Tree

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

Method Detail

setDatabase

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


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.


getMaxLNs

public long getMaxLNs()
Cheaply calculates and returns the maximum possible number of LNs in the btree.


getTreeStats

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

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

latchRootLatchExclusive

public void latchRootLatchExclusive()
                             throws DatabaseException
Throws:
DatabaseException

releaseRootLatch

public void releaseRootLatch()
                      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

getFirstNode

public IN getFirstNode(CacheMode cacheMode)
                throws DatabaseException
Find the leftmost node (IN or BIN) in the 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 IN getLastNode(CacheMode cacheMode)
               throws DatabaseException
Find the rightmost node (IN or BIN) in the 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,
                                          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 targetIsRoot,
                                          byte[] targetTreeKey,
                                          boolean requireExactMatch,
                                          CacheMode cacheMode,
                                          int targetLevel,
                                          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[] key,
                                      boolean splitsAllowed,
                                      boolean findDeletedEntries,
                                      CacheMode cacheMode)
                               throws DatabaseException
Return a reference to the parent of this LN. This searches through the 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.
key - key to navigate through main key
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.
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,
                      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.
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,
                      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.
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,
                 BINBoundary binBoundary,
                 CacheMode cacheMode,
                 Comparator<byte[]> searchComparator)
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.
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.

searchSplitsAllowed

public IN searchSplitsAllowed(byte[] key,
                              CacheMode cacheMode,
                              Comparator<byte[]> searchComparator)
Do a key based search, permitting pre-emptive splits. Returns the target node's parent.


loadStats

public void loadStats(StatsConfig config,
                      BtreeStats btreeStats)

searchDeletableSubTree

public void searchDeletableSubTree(IN parent,
                                   byte[] key,
                                   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

findBinForInsert

public void findBinForInsert(byte[] key,
                             CursorImpl cursor)
Find the BIN that is relevant to the insert. If the tree doesn't exist yet, then create the first IN and BIN. On return, the cursor is set to the BIN that is found or created, and the BIN is latched.


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(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(ByteBuffer itemBuffer,
                        int 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, int)

dumpLog

public void dumpLog(StringBuilder 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.StringBuilder, 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()

dumpString

public String dumpString(int nSpaces)

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)

setCkptHook

public void setCkptHook(TestHook hook)


Copyright (c) 2004-2012 Oracle. All rights reserved.