|
|||||||||
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. 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 |
---|
public Tree(DatabaseImpl database) throws DatabaseException
DatabaseException
public Tree()
Method Detail |
---|
public void setDatabase(DatabaseImpl database) throws DatabaseException
DatabaseException
public DatabaseImpl getDatabase()
public void setRoot(ChildReference newRoot)
TreeStats getTreeStats()
public void setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)
public IN withRootLatched(WithRootLatched wrl) throws DatabaseException
DatabaseException
public boolean delete(byte[] idKey, UtilizationTracker tracker) throws DatabaseException
idKey
- - the identifier key of the node to delete.tracker
- is used for tracking obsolete node info.
DatabaseException
public boolean deleteDup(byte[] idKey, byte[] dupKey, UtilizationTracker tracker) throws DatabaseException
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.
DatabaseException
public IN getFirstNode() throws DatabaseException
DatabaseException
public IN getLastNode() throws DatabaseException
DatabaseException
public DBIN getFirstNode(DIN duplicateRoot) throws DatabaseException
DatabaseException
public DBIN getLastNode(DIN duplicateRoot) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, boolean updateGeneration) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, boolean updateGeneration, int targetLevel, List 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.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.
DatabaseException
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
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.
DatabaseException
public boolean getParentBINForChildLN(TreeLocation location, byte[] mainKey, byte[] dupKey, LN ln, boolean splitsAllowed, boolean findDeletedEntries, boolean searchDupTree, boolean updateGeneration) 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.mainKey
- key to navigate through main keydupKey
- key to navigate through duplicate tree. May be null, since
deleted lns have no data.ln
- the node instantiated from the logsplitsAllowed
- 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.
DatabaseException
public BIN getNextBin(BIN bin, DIN duplicateRoot) throws DatabaseException
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.
DatabaseException
public BIN getPrevBin(BIN bin, DIN duplicateRoot) throws DatabaseException
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.
DatabaseException
public IN search(byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, boolean updateGeneration) throws DatabaseException
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.
DatabaseException
public IN searchSplitsAllowed(byte[] key, long nid, boolean updateGeneration) throws DatabaseException
DatabaseException
public IN searchSubTree(IN parent, byte[] key, Tree.SearchType searchType, long nid, BINBoundary binBoundary, boolean updateGeneration) throws DatabaseException
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.
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 RIGHTsearchType
- - 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.
NodeNotEmptyException
- if DELETE was passed as a parameter and
the lowest level BIN at the bottom of the tree was not empty.
DatabaseException
public boolean insert(LN ln, byte[] key, boolean allowDuplicates, CursorImpl cursor, LockResult lnLock) throws DatabaseException
ln
- The LN to insert into the tree.key
- Key value for the nodeallowDuplicates
- whether to allow duplicates to be insertedcursor
- the cursor to update to point to the newly inserted
key/data pair, or null if no cursor should be updated.
DatabaseException
public int getLogSize()
getLogSize
in interface LogWritable
LogWritable.getLogSize()
public void writeToLog(ByteBuffer logBuffer)
LogWritable
writeToLog
in interface LogWritable
logBuffer
- is the destination bufferLogWritable.writeToLog(java.nio.ByteBuffer)
public void readFromLog(ByteBuffer itemBuffer, byte entryTypeVersion)
LogReadable
readFromLog
in interface LogReadable
LogReadable.readFromLog(java.nio.ByteBuffer, byte)
public void dumpLog(StringBuffer sb, boolean verbose)
LogReadable
dumpLog
in interface LogReadable
sb
- destination string bufferverbose
- if true, dump the full, verbose versionLogReadable.dumpLog(java.lang.StringBuffer, boolean)
public boolean logEntryIsTransactional()
logEntryIsTransactional
in interface LogReadable
LogReadable#isTransactional
public long getTransactionId()
getTransactionId
in interface LogReadable
LogReadable.getTransactionId()
public void rebuildINList() throws DatabaseException
DatabaseException
public void dump() throws DatabaseException
DatabaseException
public String dumpString(int nSpaces) throws DatabaseException
DatabaseException
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)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |