Examples of jdbm.btree.BTree

jdbm.btree.BTree
B+Tree persistent indexing data structure. B+Trees are optimized for block-based, random I/O storage because they store multiple keys on one tree node (called BPage). In addition, the leaf nodes directly contain (inline) the values associated with the keys, allowing a single (or sequential) disk read of all the values on the page.
B+Trees are n-airy, yeilding log(N) search cost. They are self-balancing, preventing search performance degradation when the size of the tree grows.
Keys and associated values must be Serializable objects. The user is responsible to supply a serializable Comparator object to be used for the ordering of entries, which are also called Tuple. The B+Tree allows traversing the keys in forward and reverse order using a TupleBrowser obtained from the browse() methods.
This implementation does not directly support duplicate keys, but it is possible to handle duplicates by inlining or referencing an object collection as a value.
There is no limit on key size or value size, but it is recommended to keep both as small as possible to reduce disk I/O. This is especially true for the key size, which impacts all non-leaf BPage objects. @author Alex Boisvert @version $Id: BTree.java,v 1.6 2005/06/25 23:12:31 doomdark Exp $

                // Create temporary store
                File tempDatabase = Files.createTemporayFileOf( dbFile );


                final RecordManager recordManager = RecordManagerFactory.createRecordManager( tempDatabase.getAbsolutePath(), new Properties() );
                ByteArrayComparator comparator = new ByteArrayComparator();
                final BTree index = BTree.createInstance( recordManager, comparator, serializer, DefaultSerializer.INSTANCE, 16 );
                recordManager.setNamedObject( "index", index.getRecid() );
                recordManager.commit();


                try
                {
                    sender.sendTo( new Receiver<String, IOException>()
                    {
                        int counter = 0;


                        @Override
                        public void receive( String item )
                            throws IOException
                        {
                            // Commit one batch
                            if( ( counter++ % 1000 ) == 0 )
                            {
                                recordManager.commit();
                            }


                            String id = item.substring( "{\"identity\":\"".length() );
                            id = id.substring( 0, id.indexOf( '"' ) );


                            // Insert
                            byte[] stateArray = item.getBytes( "UTF-8" );
                            long stateIndex = recordManager.insert( stateArray, serializer );
                            index.insert( id.getBytes( "UTF-8" ), stateIndex, false );
                        }
                    } );
                }
                catch( IOException e )
                {

View Full Code Here

    
                return set.getFirst();
            }
    
            // Handle values if they are stored in another BTree
            BTree tree = getBTree( values.getBTreeRedirect() );
    
            jdbm.helper.Tuple tuple = new jdbm.helper.Tuple();
            TupleBrowser<K, V> browser = tree.browse();
            browser.getNext( tuple );
            this.closeBrowser( browser );
            //noinspection unchecked
    
            return ( V ) tuple.getKey();

View Full Code Here

                    return;
                }


                if ( set.size() > numDupLimit )
                {
                    BTree tree = convertToBTree( set );
                    BTreeRedirect redirect = new BTreeRedirect( tree.getRecordId() );
                    bt.insert( key, ( V ) BTreeRedirectMarshaller.INSTANCE.serialize( redirect ), true );


                    if ( LOG.isDebugEnabled() )
                    {
                        LOG.debug( "<--- Add new BTREE {} = {}", name, key );
                    }
                }
                else
                {
                    bt.insert( key, ( V ) marshaller.serialize( set ), true );


                    if ( LOG.isDebugEnabled() )
                    {
                        LOG.debug( "<--- Add AVL {} = {}", name, key );
                    }
                }


                count++;
                return;
            }


            BTree tree = getBTree( values.getBTreeRedirect() );
            replaced = ( V ) tree.insert( value, StringConstants.EMPTY_BYTES, true );


            if ( replaced == null )
            {
                count++;
            }

View Full Code Here


                return;
            }


            // if the number of duplicates falls below the numDupLimit value
            BTree tree = getBTree( values.getBTreeRedirect() );


            if ( tree.find( value ) != null && tree.remove( value ) != null )
            {
                /*
                 * If we drop below the duplicate limit then we revert from using
                 * a Jdbm BTree to using an in memory AvlTree.
                 */
                if ( tree.size() <= numDupLimit )
                {
                    ArrayTree<V> avlTree = convertToArrayTree( tree );
                    bt.insert( key, ( V ) marshaller.serialize( avlTree ), true );
                    recMan.delete( tree.getRecordId() );
                }


                count--;


                if ( LOG.isDebugEnabled() )

View Full Code Here


            byte[] serialized = ( byte[] ) returned;


            if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
            {
                BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
                this.count -= tree.size();


                if ( LOG.isDebugEnabled() )
                {
                    LOG.debug( "<--- Remove BTree {} = {}", name, key );
                }


                recMan.delete( tree.getRecordId() );
                duplicateBtrees.remove( tree.getRecordId() );


                return;
            }
            else
            {

View Full Code Here


        byte[] serialized = ( byte[] ) raw;


        if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
        {
            BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
            return new KeyTupleBTreeCursor<K, V>( tree, key, valueComparator );
        }


        ArrayTree<V> set = marshaller.deserialize( serialized );

View Full Code Here


        byte[] serialized = ( byte[] ) raw;


        if ( BTreeRedirectMarshaller.isRedirect( serialized ) )
        {
            BTree tree = getBTree( BTreeRedirectMarshaller.INSTANCE.deserialize( serialized ) );
            return new KeyBTreeCursor<V>( tree, valueComparator );
        }


        return new ArrayTreeCursor<V>( marshaller.deserialize( serialized ) );
    }

View Full Code Here

                ArrayTree<V> set = values.getArrayTree();
                dupsCursor = new ArrayTreeCursor<V>( set );
            }
            else
            {
                BTree tree = table.getBTree( values.getBTreeRedirect() );
                dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
            }


            if ( value == null )
            {

View Full Code Here

                ArrayTree<V> set = values.getArrayTree();
                dupsCursor = new ArrayTreeCursor<V>( set );
            }
            else
            {
                BTree tree = table.getBTree( values.getBTreeRedirect() );
                dupsCursor = new KeyBTreeCursor<V>( tree, table.getValueComparator() );
            }


            if ( value == null )
            {

View Full Code Here

            {
                dupsCursor = new ArrayTreeCursor<V>( values.getArrayTree() );
            }
            else
            {
                BTree bt = table.getBTree( values.getBTreeRedirect() );
                dupsCursor = new KeyBTreeCursor<V>( bt, table.getValueComparator() );
            }


            /*
             * Since only tables with duplicate keys enabled use this

View Full Code Here

0 1 2 3 4 5 6 7 8 9

TOP

Related Classes of jdbm.btree.BTree

FamousPeople

jdbm.btree.StreamCorrupted

jdbm.btree.TestInsertPerf

jdbm.helper.Tuple

jdbm.helper.TupleBrowser

jdbm.htree.TestRollback

org.activemq.store.jdbm.JdbmPersistenceAdapter

org.apache.directory.server.core.partition.impl.btree.jdbm.DupsCursor

org.apache.directory.server.core.partition.impl.btree.jdbm.JdbmTable

org.apache.directory.server.core.partition.impl.btree.jdbm.KeyTupleBTreeCursorTest

All source code are property of their respective owners. Java is a trademark of Sun Microsystems, Inc and owned by ORACLE Inc. Contact coftware#gmail.com.