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 $

      commit();
   }


   @Override
   public String toString() {
      BTree et = expiryTree;
      int expiry = (et == null) ? -1 : et.size();
      return "JdbmCacheLoader locationStr=" + config.getLocation() + " expirySize=" + expiry;
   }

View Full Code Here

    
    }


    private BTree getDupsContainer() throws Exception
    {
        BTree tree = table.getBTree();
        
        DupsContainer<String> values = table.getDupsContainer( ( byte[] ) tree.find( KEY ) );
        
        return table.getBTree( values.getBTreeRedirect() );   
    }

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();
        tree.browse().getNext( tuple );
        //noinspection unchecked
        
        return ( V ) tuple.getKey();
    }

View Full Code Here

            V result = set.findGreaterOrEqual( val );
            return result != null;
        }


        // last option is to try a btree with BTreeRedirects
        BTree tree = getBTree( values.getBTreeRedirect() );
        
        return tree.size() != 0 && btreeHas( tree, val, true );
    }

View Full Code Here

            V result = set.findLessOrEqual( val );
            return result != null;
        }


        // last option is to try a btree with BTreeRedirects
        BTree tree = getBTree( values.getBTreeRedirect() );
        
        return tree.size() != 0 && btreeHas( tree, val, false );
    }

View Full Code Here

                {
                    return;
                }
                if ( set.size() > numDupLimit )
                {
                    BTree tree = convertToBTree( set );
                    BTreeRedirect redirect = new BTreeRedirect( tree.getRecid() );
                    bt.insert( key, BTreeRedirectMarshaller.INSTANCE.serialize( redirect ), true );
                    
                    if ( LOG.isDebugEnabled() )
                    {
                        LOG.debug( "<--- Add new BTREE {} = {}", name, key );
                    }
                }
                else
                {
                    bt.insert( key, 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, StringTools.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 )
            {
                if ( 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, marshaller.serialize( avlTree ), true );
                        recMan.delete( tree.getRecid() );
                    }
                    
                    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.getRecid() );
                duplicateBtrees.remove( tree.getRecid() );
                return;
            }
            else
            {
                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 KeyTupleBTreeCursor<K,V>( tree, key, valueComparator );
        }


        ArrayTree<V> set = marshaller.deserialize( serialized );
        return new KeyTupleArrayCursor<K,V>( set, key );

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

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.