Menu
▾
▴
[cweb-CVS] bigdata/src/java/com/bigdata/btree BTree.java, 1.3, 1.4 EntryIterator.java, 1.1, 1.2 BTreeMetadata.java, 1.2, 1.3 PO.java, 1.1, 1.2 AbstractBTree.java, 1.2, 1.3 AbstractNode.java, 1.1, 1.2
|
From: Bryan T. <tho...@us...> - 2007-04-18 17:29:26
|
Update of /cvsroot/cweb/bigdata/src/java/com/bigdata/btree In directory sc8-pr-cvs4.sourceforge.net:/tmp/cvs-serv23060/src/java/com/bigdata/btree Modified Files: BTree.java EntryIterator.java BTreeMetadata.java PO.java AbstractBTree.java AbstractNode.java Log Message: testing SAIL and lubm, including adding BTree#removeAll(), touching up some inferences, making it possible to load different RDF interchange formats, and adding JOIN ordering based on the sesame optimizer and the actual triple pattern selectivity in the data. Index: AbstractNode.java =================================================================== RCS file: /cvsroot/cweb/bigdata/src/java/com/bigdata/btree/AbstractNode.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** AbstractNode.java 13 Apr 2007 15:04:13 -0000 1.1 --- AbstractNode.java 18 Apr 2007 17:29:20 -0000 1.2 *************** *** 579,582 **** --- 579,593 ---- * FIXME when using an {@link IndexSegment} provide for direct leaf * successor scans. + * + * FIXME Support update of the current value for an entry, delete of the + * entry, and insert of an entry into the current leaf. + * <p> + * <p> + * Note that if there are persistent nodes in the tree, then copy-on-write + * is triggered during traversal. In order for us to write an iterator-based + * delete of the existing keys (causing them to become "delete" markers) we + * need the iterator to handle concurrent modification, at least to the + * extent that it can follow the change from the persistent reference for a + * node to the new mutable reference for that node. */ private static class PostOrderEntryIterator extends Striterator implements IEntryIterator { Index: BTreeMetadata.java =================================================================== RCS file: /cvsroot/cweb/bigdata/src/java/com/bigdata/btree/BTreeMetadata.java,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** BTreeMetadata.java 16 Apr 2007 10:02:49 -0000 1.2 --- BTreeMetadata.java 18 Apr 2007 17:29:20 -0000 1.3 *************** *** 247,251 **** public static BTreeMetadata read(IRawStore store, long addr) { ! return (BTreeMetadata) SerializerUtil.deserialize(store.read(addr)); } --- 247,256 ---- public static BTreeMetadata read(IRawStore store, long addr) { ! BTreeMetadata metadata = (BTreeMetadata) SerializerUtil.deserialize(store.read(addr)); ! ! // save the address from which the metadata record was loaded. ! metadata.addrMetadata = addr; ! ! return metadata; } Index: EntryIterator.java =================================================================== RCS file: /cvsroot/cweb/bigdata/src/java/com/bigdata/btree/EntryIterator.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** EntryIterator.java 13 Apr 2007 15:04:13 -0000 1.1 --- EntryIterator.java 18 Apr 2007 17:29:20 -0000 1.2 *************** *** 273,276 **** --- 273,291 ---- /** + * FIXME Support removal. This is tricky because we have to invoke + * copy-on-write if the leaf is not dirty. Since copy-on-write can cause the + * leaf and its parents to be cloned, and since the entry must be removed in + * the mutable copy, this means that the {@link Leaf} that we have may be + * the wrong object. The simplest way to handle that is to re-start the + * iterator from the current key and then invoke delete on that entry. + * However, that is not that simple :-) <br> + * The other twist with removal is that it can cause the leaf to underflow, + * which results in a structural change in the btree. + * + * @todo Also support update of the value during traversal. This is simpler + * since it does not lead to structural changes (the #of entries in + * the leaf does not change), but it has the same problems with + * needing to invoke copy-on-write if the leaf is not dirty. + * * @exception UnsupportedOperationException */ *************** *** 292,296 **** public EntryFilter() { ! this.state = null; } --- 307,313 ---- public EntryFilter() { ! ! this( null ); ! } *************** *** 303,307 **** --- 320,326 ---- */ public EntryFilter(Object state) { + this.state = state; + } *************** *** 317,321 **** /** ! * Resolve the value that the iterator would visit This can be used to * return an application value encapsulated by an {@link IValue}, to * de-serialize application values, etc. The default implementation is a --- 336,340 ---- /** ! * Resolve the value that the iterator would visit. This can be used to * return an application value encapsulated by an {@link IValue}, to * de-serialize application values, etc. The default implementation is a Index: BTree.java =================================================================== RCS file: /cvsroot/cweb/bigdata/src/java/com/bigdata/btree/BTree.java,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** BTree.java 13 Apr 2007 15:04:12 -0000 1.3 --- BTree.java 18 Apr 2007 17:29:20 -0000 1.4 *************** *** 52,55 **** --- 52,57 ---- import com.bigdata.cache.HardReferenceQueue; import com.bigdata.journal.ICommitter; + import com.bigdata.journal.IIndexManager; + import com.bigdata.journal.IJournal; import com.bigdata.rawstore.Addr; import com.bigdata.rawstore.IRawStore; *************** *** 434,438 **** --- 436,454 ---- */ assert hardReferenceQueue.capacity() >= MINIMUM_LEAF_QUEUE_CAPACITY; + + /* + * Setup the initial root leaf. + */ + newRootLeaf(); + } + + /** + * Creates and sets new root {@link Leaf} on the B+Tree and (re)sets the + * various counters to be consistent with that root. This is used both + * by the constructor for a new {@link BTree} and by {@link #removeAll()}. + */ + private void newRootLeaf() { + this.height = 0; *************** *** 444,449 **** this.nleaves = 1; - } /** * Load an existing B+Tree from the store. --- 460,466 ---- this.nleaves = 1; + } + /** * Load an existing B+Tree from the store. *************** *** 674,706 **** /** ! * Not implement yet. ! * ! * @todo Define the semantics for deleting the btree. If the delete is on an ! * unisolated btree then all we need to do is replace the root with an ! * empty root leaf. Old nodes and leaves will be swept from the store ! * eventually when the journal overflows. ! * <p> ! * If the delete occurs during a transaction the isolation means that ! * we have to delete all of the keys, causing "delete" entries to ! * spring into existance for each key in the tree. When the ! * transaction commits, those delete markers will have to validate ! * against the global state of the tree. If the transaction validates, ! * then the merge down onto the global state will cause the ! * corresponding entries to be removed from the global tree. ! * <p> ! * Note that if there are persistent nodes in the tree, then ! * copy-on-write is triggered during traversal. In order for us to ! * write an iterator-based delete of the existing keys (causing them ! * to become "delete" markers) we need the iterator to handle ! * concurrent modification, at least to the extent that it can follow ! * the change from the persistent reference for a node to the new ! * mutable reference for that node. ! * <p> ! * Note that there is probably processing order that is more efficient ! * for delete, e.g., left-to-right vs right-to-left. */ ! public void delete() { ! throw new UnsupportedOperationException(); } --- 691,725 ---- /** ! * Remove all entries in the B+Tree. ! * <p> ! * This implementation simply replaces the root with a new root leaf and ! * resets the counters (height, #of nodes, #of leaves, etc). to be ! * consistent with that new root. If the btree is then made restart-safe by ! * the commit protocol of the backing store then the effect is as if all ! * entries had been deleted. Old nodes and leaves will be swept from the ! * store eventually when the journal overflows. ! * <p> ! * Note: This implementation simply replaces the root node with a new root ! * leaf and does not release storage for nodes and leaves in the B+Tree. ! * This is because the overall design for bigdata combines an append only ! * {@link IJournal} with overflow onto read-only {@link IndexSegment}s. Old ! * journals are simply deleted, thereby reclaiming the storage on the file ! * system. ! * <p> ! * Note: This implementation is overriden in the ! * <code>com.btree.isolation</code> package since isolation requires ! * writing explicit delete markers for each entry in the B+Tree. ! * <p> ! * Note: The {@link IIndexManager} defines methods for registering (adding) ! * and dropping indices. The {@link IIndexManager#dropIndex(String)} method ! * should be used to remove a scale-out partitioned index. */ ! public void removeAll() { ! /* ! * Replace the root with a new root leaf. ! */ ! ! newRootLeaf(); } Index: AbstractBTree.java =================================================================== RCS file: /cvsroot/cweb/bigdata/src/java/com/bigdata/btree/AbstractBTree.java,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** AbstractBTree.java 16 Apr 2007 10:02:49 -0000 1.2 --- AbstractBTree.java 18 Apr 2007 17:29:20 -0000 1.3 *************** *** 49,53 **** import java.io.PrintStream; - import java.lang.ref.WeakReference; import java.nio.ByteBuffer; import java.util.Iterator; --- 49,52 ---- Index: PO.java =================================================================== RCS file: /cvsroot/cweb/bigdata/src/java/com/bigdata/btree/PO.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** PO.java 13 Apr 2007 15:04:11 -0000 1.1 --- PO.java 18 Apr 2007 17:29:20 -0000 1.2 *************** *** 52,58 **** * @author <a href="mailto:tho...@us...">Bryan Thompson</a> * @version $Id$ - * - * @todo This abstract class is only used by the {@link BTree}. Modify it so - * that we directly test the member fields for better performance. */ abstract public class PO implements IIdentityAccess, IDirty { --- 52,55 ---- |
