|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.sleepycat.je.tree.Tree
public final class Tree
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 |
---|
public Tree(DatabaseImpl database)
public Tree()
Method Detail |
---|
public void setDatabase(DatabaseImpl database)
public DatabaseImpl getDatabase()
public void setRoot(ChildReference newRoot, boolean notLatched)
public ChildReference makeRootChildReference(Node target, byte[] key, long lsn)
public boolean rootExists()
public boolean isRootResident()
public long getRootLsn()
public long getMaxLNs()
int getTreeStats()
public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)
public IN withRootLatchedExclusive(WithRootLatched wrl) throws DatabaseException
DatabaseException
public IN withRootLatchedShared(WithRootLatched wrl) throws DatabaseException
DatabaseException
public void latchRootLatchExclusive() throws DatabaseException
DatabaseException
public void releaseRootLatch() throws DatabaseException
DatabaseException
public void delete(byte[] idKey, LocalUtilizationTracker localTracker) throws DatabaseException, NodeNotEmptyException, CursorsExistException
idKey
- - the identifier key of the node to delete.localTracker
- is used for tracking obsolete node info.
DatabaseException
NodeNotEmptyException
CursorsExistException
public IN getFirstNode(CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN getLastNode(CacheMode cacheMode) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, CacheMode cacheMode) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, CacheMode cacheMode, int targetLevel, List<TrackingInfo> trackingList) throws DatabaseException
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.
DatabaseException
public SearchResult getParentINForChildIN(long targetNodeId, boolean targetIsRoot, byte[] targetTreeKey, boolean requireExactMatch, CacheMode cacheMode, int targetLevel, List<TrackingInfo> trackingList, boolean doFetch) throws DatabaseException
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.
DatabaseException
public boolean getParentBINForChildLN(TreeLocation location, byte[] key, boolean splitsAllowed, boolean findDeletedEntries, CacheMode cacheMode) throws DatabaseException
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.
location
- a holder class to hold state about the location
of our search. Sort of an internal cursor.key
- key to navigate through main keysplitsAllowed
- 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.
DatabaseException
public BIN getNextBin(BIN bin, CacheMode cacheMode) throws DatabaseException
bin
- The BIN to find the next BIN for. This BIN is latched.
DatabaseException
public BIN getPrevBin(BIN bin, CacheMode cacheMode) throws DatabaseException
bin
- The BIN to find the next BIN for. This BIN is latched.
DatabaseException
public IN search(byte[] key, Tree.SearchType searchType, BINBoundary binBoundary, CacheMode cacheMode, Comparator<byte[]> searchComparator)
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.
public IN searchSplitsAllowed(byte[] key, CacheMode cacheMode, Comparator<byte[]> searchComparator)
public void loadStats(StatsConfig config, BtreeStats btreeStats)
public void searchDeletableSubTree(IN parent, byte[] key, ArrayList<com.sleepycat.je.tree.Tree.SplitInfo> nodeLadder) throws DatabaseException, NodeNotEmptyException, CursorsExistException
DatabaseException
NodeNotEmptyException
CursorsExistException
public IN getRootIN(CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN getRootINLatchedExclusive(CacheMode cacheMode) throws DatabaseException
DatabaseException
public IN getResidentRootIN(boolean latched) throws DatabaseException
DatabaseException
public void findBinForInsert(byte[] key, CursorImpl cursor)
public int getLogSize()
getLogSize
in interface Loggable
Loggable.getLogSize()
public void writeToLog(ByteBuffer logBuffer)
Loggable
writeToLog
in interface Loggable
logBuffer
- is the destination bufferLoggable.writeToLog(java.nio.ByteBuffer)
public void readFromLog(ByteBuffer itemBuffer, int entryVersion)
Loggable
readFromLog
in interface Loggable
Loggable.readFromLog(java.nio.ByteBuffer, int)
public void dumpLog(StringBuilder sb, boolean verbose)
Loggable
dumpLog
in interface Loggable
sb
- destination string bufferverbose
- if true, dump the full, verbose versionLoggable.dumpLog(java.lang.StringBuilder, boolean)
public long getTransactionId()
getTransactionId
in interface Loggable
Loggable.getTransactionId()
public boolean logicalEquals(Loggable other)
logicalEquals
in interface Loggable
Always return false, this item should never be compared.
public void rebuildINList() throws DatabaseException
DatabaseException
public void dump()
public String dumpString(int nSpaces)
boolean validateDelete(int index) throws DatabaseException
DatabaseException
public void validateINList(IN parent) throws DatabaseException
DatabaseException
public void setWaitHook(TestHook hook)
public void setSearchHook(TestHook hook)
public void setCkptHook(TestHook hook)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |