|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.sleepycat.je.tree.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(Key idKey,
Set modifiedFileSummaries)
Deletes a BIN specified by key from the tree. |
boolean |
deleteDup(Key idKey,
Key dupKey,
Set modifiedFileSummaries)
Delete a subtree of a duplicate tree. |
void |
dump()
|
(package private) void |
dumpKeys()
|
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,
Key mainKey,
Key dupKey,
LN ln,
boolean splitsAllowed,
boolean findDeletedEntries,
boolean searchDupTree)
Return a reference to the parent of this LN. |
SearchResult |
getParentINForChildIN(IN child,
boolean requireExactMatch)
GetParentNode without optional tracking. |
SearchResult |
getParentINForChildIN(IN child,
boolean requireExactMatch,
List trackingList)
Return a reference to the parent or possible parent of the child. |
SearchResult |
getParentINForChildIN(long targetNodeId,
boolean targetContainsDuplicates,
boolean targetIsRoot,
Key targetMainTreeKey,
Key targetDupTreeKey,
boolean requireExactMatch,
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,
Key key,
boolean allowDuplicates,
CursorImpl cursor,
LockResult lnLock)
Inserts a new LN into the tree. |
boolean |
logEntryIsTransactional()
|
void |
readFromLog(ByteBuffer itemBuffer)
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(Key key,
Tree.SearchType searchType,
long nid,
BINBoundary binBoundary)
Search the tree, starting at the root. |
IN |
searchSubTree(IN parent,
Key key,
Tree.SearchType searchType,
long nid,
BINBoundary binBoundary)
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 |
setTreeStatsAccumulator(TreeWalkerStatsAccumulator tSA)
|
(package private) boolean |
validateDelete(int index)
Unit test support to validate subtree pruning. |
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
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(Key idKey, Set modifiedFileSummaries) throws DatabaseException
idKey
- - the identifier key of the node to delete.modifiedFileSummaries
- - a set of Long file numbers to be filled
in when INs are deleted and made obsolete.
DatabaseException
public boolean deleteDup(Key idKey, Key dupKey, Set modifiedFileSummaries) 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.modifiedFileSummaries
- - a set of Long file numbers to be filled
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) throws DatabaseException
DatabaseException
public SearchResult getParentINForChildIN(IN child, boolean requireExactMatch, 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.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, Key targetMainTreeKey, Key targetDupTreeKey, boolean requireExactMatch, List trackingList, boolean doFetch) throws DatabaseException
requireExactMatch
- if true, we must find the exact parent, not a
potential parent.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, Key mainKey, Key dupKey, LN ln, boolean splitsAllowed, boolean findDeletedEntries, boolean searchDupTree) throws DatabaseException
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.
DatabaseException
public BIN getNextBin(BIN bin, DIN duplicateRoot) throws DatabaseException
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
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(Key key, Tree.SearchType searchType, long nid, BINBoundary binBoundary) 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 searchSubTree(IN parent, Key key, Tree.SearchType searchType, long nid, BINBoundary binBoundary) 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, Key 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)
LogReadable
readFromLog
in interface LogReadable
LogReadable.readFromLog(java.nio.ByteBuffer)
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
void dumpKeys() throws DatabaseException
DatabaseException
boolean validateDelete(int index) throws DatabaseException
DatabaseException
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |