com.sleepycat.je.tree

Class Tree

java.lang.Object

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

Nested Classes

Modifier and Type	Class and Description
static class	Tree.SearchType Embodies an enum for the type of search being performed.

Constructor Summary

Constructors

Constructor and Description
Tree() Create a tree that's being read in from the log.
Tree(DatabaseImpl database) Create a new tree.

Method Summary

Methods

Modifier and Type	Method and Description
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()
(package private) TreeStats	getTreeStats()
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)
(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(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.

getTreeStats

TreeStats 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

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

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)