View Javadoc
1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License.
18   *
19   */
20  package org.apache.directory.mavibot.btree;
21  
22  
23  import java.io.Closeable;
24  import java.io.IOException;
25  import java.nio.ByteBuffer;
26  import java.nio.channels.FileChannel;
27  import java.util.concurrent.ConcurrentLinkedQueue;
28  
29  import org.apache.commons.collections.map.LRUMap;
30  import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
31  import org.slf4j.Logger;
32  import org.slf4j.LoggerFactory;
33  
34  
35  /**
36   * The B+Tree MVCC data structure.
37   *
38   * @param <K> The type for the keys
39   * @param <V> The type for the stored values
40   *
41   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
42   */
43  public class PersistedBTree<K, V> extends AbstractBTree<K, V> implements Closeable
44  {
45      /** The LoggerFactory used by this class */
46      protected static final Logger LOG = LoggerFactory.getLogger( PersistedBTree.class );
47  
48      protected static final Logger LOG_PAGES = LoggerFactory.getLogger( "org.apache.directory.mavibot.LOG_PAGES" );
49  
50      /** The cache associated with this B-tree */
51      protected LRUMap cache;
52  
53      /** The default number of pages to keep in memory */
54      public static final int DEFAULT_CACHE_SIZE = 1000;
55  
56      /** The cache size, default to 1000 elements */
57      protected int cacheSize = DEFAULT_CACHE_SIZE;
58  
59      /** The number of stored Values before we switch to a B-tree */
60      private static final int DEFAULT_VALUE_THRESHOLD_UP = 8;
61  
62      /** The number of stored Values before we switch back to an array */
63      private static final int DEFAULT_VALUE_THRESHOLD_LOW = 1;
64  
65      /** The configuration for the array <-> B-tree switch */
66      /*No qualifier*/static int valueThresholdUp = DEFAULT_VALUE_THRESHOLD_UP;
67      /*No qualifier*/static int valueThresholdLow = DEFAULT_VALUE_THRESHOLD_LOW;
68  
69      /** The BtreeInfo offset */
70      private long btreeInfoOffset = RecordManager.NO_PAGE;
71  
72      /** The internal recordManager */
73      private RecordManager recordManager;
74  
75  
76      /**
77       * Creates a new BTree, with no initialization.
78       */
79      /* no qualifier */PersistedBTree()
80      {
81          setType( BTreeTypeEnum.PERSISTED );
82      }
83  
84  
85      /**
86       * Creates a new persisted B-tree using the BTreeConfiguration to initialize the
87       * BTree
88       *
89       * @param configuration The configuration to use
90       */
91      /* no qualifier */PersistedBTree( PersistedBTreeConfiguration<K, V> configuration )
92      {
93          super();
94          String name = configuration.getName();
95  
96          if ( name == null )
97          {
98              throw new IllegalArgumentException( "BTree name cannot be null" );
99          }
100 
101         setName( name );
102         setPageSize( configuration.getPageSize() );
103         setKeySerializer( configuration.getKeySerializer() );
104         setValueSerializer( configuration.getValueSerializer() );
105         setAllowDuplicates( configuration.isAllowDuplicates() );
106         setType( configuration.getBtreeType() );
107 
108         readTimeOut = configuration.getReadTimeOut();
109         writeBufferSize = configuration.getWriteBufferSize();
110         cacheSize = configuration.getCacheSize();
111 
112         if ( keySerializer.getComparator() == null )
113         {
114             throw new IllegalArgumentException( "Comparator should not be null" );
115         }
116 
117         // Create the first root page, with revision 0L. It will be empty
118         // and increment the revision at the same time
119         Page<K, V> rootPage = new PersistedLeaf<K, V>( this );
120 
121         // Create a B-tree header, and initialize it
122         BTreeHeader<K, V> btreeHeader = new BTreeHeader<K, V>();
123         btreeHeader.setRootPage( rootPage );
124         btreeHeader.setBtree( this );
125 
126         switch ( btreeType )
127         {
128             case BTREE_OF_BTREES:
129             case COPIED_PAGES_BTREE:
130                 // We will create a new cache and a new readTransactions map 
131                 init( null );
132                 currentBtreeHeader = btreeHeader;
133                 break;
134 
135             case PERSISTED_SUB:
136                 init( ( PersistedBTree<K, V> ) configuration.getParentBTree() );
137                 btreeRevisions.put( 0L, btreeHeader );
138                 currentBtreeHeader = btreeHeader;
139                 break;
140 
141             default:
142                 // We will create a new cache and a new readTransactions map 
143                 init( null );
144                 btreeRevisions.put( 0L, btreeHeader );
145                 currentBtreeHeader = btreeHeader;
146                 break;
147         }
148     }
149 
150 
151     /**
152      * Initialize the BTree.
153      *
154      * @throws IOException If we get some exception while initializing the BTree
155      */
156     public void init( BTree<K, V> parentBTree )
157     {
158         if ( parentBTree == null )
159         {
160             // This is not a subBtree, we have to initialize the cache
161 
162             // Create the queue containing the pending read transactions
163             readTransactions = new ConcurrentLinkedQueue<ReadTransaction<K, V>>();
164 
165             if ( cacheSize < 1 )
166             {
167                 cacheSize = DEFAULT_CACHE_SIZE;
168             }
169 
170             cache = new LRUMap( cacheSize );
171         }
172         else
173         {
174             this.cache = ( ( PersistedBTree<K, V> ) parentBTree ).getCache();
175             this.readTransactions = ( ( PersistedBTree<K, V> ) parentBTree ).getReadTransactions();
176         }
177 
178         // Initialize the txnManager thread
179         //FIXME we should NOT create a new transaction manager thread for each BTree
180         //createTransactionManager();
181     }
182 
183 
184     /**
185      * Return the cache we use in this BTree
186      */
187     /* No qualifier */LRUMap getCache()
188     {
189         return cache;
190     }
191 
192 
193     /**
194      * Return the cache we use in this BTree
195      */
196     /* No qualifier */ConcurrentLinkedQueue<ReadTransaction<K, V>> getReadTransactions()
197     {
198         return readTransactions;
199     }
200 
201 
202     /**
203      * Close the BTree, cleaning up all the data structure
204      */
205     public void close() throws IOException
206     {
207         // Stop the readTransaction thread
208         // readTransactionsThread.interrupt();
209         // readTransactions.clear();
210 
211         // Clean the cache
212         cache.clear();
213     }
214 
215 
216     /**
217      * @return the btreeOffset
218      */
219     /* No qualifier*/long getBtreeOffset()
220     {
221         return getBTreeHeader( getName() ).getBTreeHeaderOffset();
222     }
223 
224 
225     /**
226      * @param btreeOffset the B-tree header Offset to set
227      */
228     /* No qualifier*/void setBtreeHeaderOffset( long btreeHeaderOffset )
229     {
230         getBTreeHeader( getName() ).setBTreeHeaderOffset( btreeHeaderOffset );
231     }
232 
233 
234     /**
235      * @return the rootPageOffset
236      */
237     /* No qualifier*/long getRootPageOffset()
238     {
239         return getBTreeHeader( getName() ).getRootPageOffset();
240     }
241 
242 
243     /**
244      * Gets the RecordManager for a managed BTree
245      *
246      * @return The recordManager if the B-tree is managed
247      */
248     /* No qualifier */RecordManager getRecordManager()
249     {
250         return recordManager;
251     }
252 
253 
254     /**
255      * Inject a RecordManager for a managed BTree
256      *
257      * @param recordManager The injected RecordManager
258      */
259     /* No qualifier */void setRecordManager( RecordManager recordManager )
260     {
261         // The RecordManager is also the TransactionManager
262         transactionManager = recordManager;
263         this.recordManager = recordManager;
264     }
265 
266 
267     /**
268      *
269      * Deletes the given <key,value> pair if both key and value match. If the given value is null
270      * and there is no null value associated with the given key then the entry with the given key
271      * will be removed.
272      *
273      * @param key The key to be removed
274      * @param value The value to be removed (can be null, and when no null value exists the key will be removed irrespective of the value)
275      * @param revision The revision to be associated with this operation
276      * @return
277      * @throws IOException
278      */
279     /* no qualifier */Tuple<K, V> delete( K key, V value, long revision ) throws IOException
280     {
281         // We have to start a new transaction, which will be committed or rollbacked
282         // locally. This will duplicate the current BtreeHeader during this phase.
283         if ( revision == -1L )
284         {
285             revision = currentRevision.get() + 1;
286         }
287 
288         try
289         {
290             // Try to delete the entry starting from the root page. Here, the root
291             // page may be either a Node or a Leaf
292             DeleteResult<K, V> result = processDelete( key, value, revision );
293 
294             // Check that we have found the element to delete
295             if ( result instanceof NotPresentResult )
296             {
297                 // We haven't found the element in the B-tree, just get out
298                 // without updating the recordManager
299 
300                 return null;
301             }
302 
303             // The element was found, and removed
304             AbstractDeleteResult<K, V> deleteResult = ( AbstractDeleteResult<K, V> ) result;
305 
306             Tuple<K, V> tuple = deleteResult.getRemovedElement();
307 
308             // If the B-tree is managed, we have to update the rootPage on disk
309             // Update the RecordManager header
310 
311             // Return the value we have found if it was modified
312             return tuple;
313         }
314         catch ( IOException ioe )
315         {
316             // if we've got an error, we have to rollback
317             throw ioe;
318         }
319     }
320 
321 
322     /**
323      * Insert the tuple into the B-tree rootPage, get back the new rootPage
324      */
325     private DeleteResult<K, V> processDelete( K key, V value, long revision ) throws IOException
326     {
327         // Get the current B-tree header, and delete the value from it
328         BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
329 
330         // Try to delete the entry starting from the root page. Here, the root
331         // page may be either a Node or a Leaf
332         DeleteResult<K, V> result = btreeHeader.getRootPage().delete( key, value, revision );
333 
334         if ( result instanceof NotPresentResult )
335         {
336             // Key not found.
337             return result;
338         }
339 
340         // Create a new BTreeHeader
341         BTreeHeader<K, V> newBtreeHeader = btreeHeader.copy();
342 
343         // Inject the old B-tree header into the pages to be freed
344         // if we are deleting an element from a management BTree
345         if ( ( btreeType == BTreeTypeEnum.BTREE_OF_BTREES ) || ( btreeType == BTreeTypeEnum.COPIED_PAGES_BTREE ) )
346         {
347             PageIO[] pageIos = recordManager.readPageIOs( btreeHeader.getBTreeHeaderOffset(), -1L );
348 
349             for ( PageIO pageIo : pageIos )
350             {
351                 recordManager.freedPages.add( pageIo );
352             }
353         }
354 
355         // The element was found, and removed
356         AbstractDeleteResult<K, V> removeResult = ( AbstractDeleteResult<K, V> ) result;
357 
358         // This is a new root
359         Page<K, V> newRootPage = removeResult.getModifiedPage();
360 
361         // Write the modified page on disk
362         // Note that we don't use the holder, the new root page will
363         // remain in memory.
364         writePage( newRootPage, revision );
365 
366         // Decrease the number of elements in the current tree
367         newBtreeHeader.decrementNbElems();
368         newBtreeHeader.setRootPage( newRootPage );
369         newBtreeHeader.setRevision( revision );
370 
371         // Write down the data on disk
372         long newBtreeHeaderOffset = recordManager.writeBtreeHeader( this, newBtreeHeader );
373 
374         // Update the B-tree of B-trees with this new offset, if we are not already doing so
375         switch ( btreeType )
376         {
377             case PERSISTED:
378                 // We have a new B-tree header to inject into the B-tree of btrees
379                 recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset );
380 
381                 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
382 
383                 // Store the new revision
384                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
385 
386                 break;
387 
388             case PERSISTED_SUB:
389                 // Sub-B-trees are only updating the CopiedPage B-tree
390                 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
391 
392                 //btreeRevisions.put( revision, newBtreeHeader );
393 
394                 currentRevision.set( revision );
395 
396                 break;
397 
398             case BTREE_OF_BTREES:
399                 // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
400                 recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
401 
402                 // We can free the copied pages
403                 recordManager.freePages( this, revision, result.getCopiedPages() );
404 
405                 // Store the new revision
406                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
407 
408                 break;
409 
410             case COPIED_PAGES_BTREE:
411                 // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
412                 recordManager.updateRecordManagerHeader( -1L, newBtreeHeaderOffset );
413 
414                 // We can free the copied pages
415                 recordManager.freePages( this, revision, result.getCopiedPages() );
416 
417                 // Store the new revision
418                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
419 
420                 break;
421 
422             default:
423                 // Nothing to do for sub-btrees
424                 break;
425         }
426 
427         // Return the value we have found if it was modified
428         return result;
429     }
430 
431 
432     /**
433      * Insert an entry in the BTree.
434      * <p>
435      * We will replace the value if the provided key already exists in the
436      * btree.
437      * <p>
438      * The revision number is the revision to use to insert the data.
439      *
440      * @param key Inserted key
441      * @param value Inserted value
442      * @param revision The revision to use
443      * @return an instance of the InsertResult.
444      */
445     /* no qualifier */InsertResult<K, V> insert( K key, V value, long revision ) throws IOException
446     {
447         // We have to start a new transaction, which will be committed or rollbacked
448         // locally. This will duplicate the current BtreeHeader during this phase.
449         if ( revision == -1L )
450         {
451             revision = currentRevision.get() + 1;
452         }
453 
454         try
455         {
456             // Try to insert the new value in the tree at the right place,
457             // starting from the root page. Here, the root page may be either
458             // a Node or a Leaf
459             InsertResult<K, V> result = processInsert( key, value, revision );
460 
461             // Return the value we have found if it was modified
462             return result;
463         }
464         catch ( IOException ioe )
465         {
466             throw ioe;
467         }
468     }
469 
470 
471     private BTreeHeader<K, V> getBTreeHeader( String name )
472     {
473         switch ( btreeType )
474         {
475             case PERSISTED_SUB:
476                 return getBtreeHeader();
477 
478             case BTREE_OF_BTREES:
479                 return recordManager.getNewBTreeHeader( RecordManager.BTREE_OF_BTREES_NAME );
480 
481             case COPIED_PAGES_BTREE:
482                 return recordManager.getNewBTreeHeader( RecordManager.COPIED_PAGE_BTREE_NAME );
483 
484             default:
485                 return recordManager.getBTreeHeader( name );
486         }
487     }
488 
489 
490     private BTreeHeader<K, V> getNewBTreeHeader( String name )
491     {
492         if ( btreeType == BTreeTypeEnum.PERSISTED_SUB )
493         {
494             return getBtreeHeader();
495         }
496 
497         BTreeHeader<K, V> btreeHeader = recordManager.getNewBTreeHeader( getName() );
498 
499         return btreeHeader;
500     }
501 
502 
503     /**
504      * Insert the tuple into the B-tree rootPage, get back the new rootPage
505      */
506     private InsertResult<K, V> processInsert( K key, V value, long revision ) throws IOException
507     {
508         // Get the current B-tree header, and insert the value into it
509         BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
510         InsertResult<K, V> result = btreeHeader.getRootPage().insert( key, value, revision );
511 
512         if ( result instanceof ExistsResult )
513         {
514             return result;
515         }
516 
517         // Create a new BTreeHeader
518         BTreeHeader<K, V> newBtreeHeader = btreeHeader.copy();
519 
520         // Inject the old B-tree header into the pages to be freed
521         // if we are inserting an element in a management BTree
522         if ( ( btreeType == BTreeTypeEnum.BTREE_OF_BTREES ) || ( btreeType == BTreeTypeEnum.COPIED_PAGES_BTREE ) )
523         {
524             PageIO[] pageIos = recordManager.readPageIOs( btreeHeader.getBTreeHeaderOffset(), -1L );
525 
526             for ( PageIO pageIo : pageIos )
527             {
528                 recordManager.freedPages.add( pageIo );
529             }
530         }
531 
532         Page<K, V> newRootPage;
533 
534         if ( result instanceof ModifyResult )
535         {
536             ModifyResult<K, V> modifyResult = ( ( ModifyResult<K, V> ) result );
537 
538             newRootPage = modifyResult.getModifiedPage();
539 
540             // Increment the counter if we have inserted a new value
541             if ( modifyResult.getModifiedValue() == null )
542             {
543                 newBtreeHeader.incrementNbElems();
544             }
545         }
546         else
547         {
548             // We have split the old root, create a new one containing
549             // only the pivotal we got back
550             SplitResult<K, V> splitResult = ( ( SplitResult<K, V> ) result );
551 
552             K pivot = splitResult.getPivot();
553             Page<K, V> leftPage = splitResult.getLeftPage();
554             Page<K, V> rightPage = splitResult.getRightPage();
555 
556             // If the B-tree is managed, we have to write the two pages that were created
557             // and to keep a track of the two offsets for the upper node
558             PageHolder<K, V> holderLeft = writePage( leftPage, revision );
559 
560             PageHolder<K, V> holderRight = writePage( rightPage, revision );
561 
562             // Create the new rootPage
563             newRootPage = new PersistedNode<K, V>( this, revision, pivot, holderLeft, holderRight );
564 
565             // Always increment the counter : we have added a new value
566             newBtreeHeader.incrementNbElems();
567         }
568 
569         // Write the new root page on disk
570         LOG_PAGES.debug( "Writing the new rootPage revision {} for {}", revision, name );
571         writePage( newRootPage, revision );
572 
573         // Update the new B-tree header
574         newBtreeHeader.setRootPage( newRootPage );
575         newBtreeHeader.setRevision( revision );
576 
577         // Write down the data on disk
578         long newBtreeHeaderOffset = recordManager.writeBtreeHeader( this, newBtreeHeader );
579 
580         // Update the B-tree of B-trees with this new offset, if we are not already doing so
581         switch ( btreeType )
582         {
583             case PERSISTED:
584                 // We have a new B-tree header to inject into the B-tree of btrees
585                 recordManager.addInBtreeOfBtrees( getName(), revision, newBtreeHeaderOffset );
586 
587                 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
588 
589                 // Store the new revision
590                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
591 
592                 break;
593 
594             case PERSISTED_SUB:
595                 // Sub-B-trees are only updating the CopiedPage B-tree
596                 recordManager.addInCopiedPagesBtree( getName(), revision, result.getCopiedPages() );
597 
598                 // Store the new revision
599                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
600 
601                 currentRevision.set( revision );
602 
603                 break;
604 
605             case BTREE_OF_BTREES:
606                 // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
607                 recordManager.updateRecordManagerHeader( newBtreeHeaderOffset, -1L );
608 
609                 // We can free the copied pages
610                 recordManager.freePages( this, revision, result.getCopiedPages() );
611 
612                 // Store the new revision
613                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
614 
615                 break;
616 
617             case COPIED_PAGES_BTREE:
618                 // The B-tree of B-trees or the copiedPages B-tree has been updated, update the RMheader parameters
619                 recordManager.updateRecordManagerHeader( -1L, newBtreeHeaderOffset );
620 
621                 // We can free the copied pages
622                 recordManager.freePages( this, revision, result.getCopiedPages() );
623 
624                 // Store the new revision
625                 storeRevision( newBtreeHeader, recordManager.isKeepRevisions() );
626 
627                 break;
628 
629             default:
630                 // Nothing to do for sub-btrees
631                 break;
632         }
633 
634         // Get the new root page and make it the current root page
635         return result;
636     }
637 
638 
639     /**
640      * Write the data in the ByteBuffer, and eventually on disk if needed.
641      *
642      * @param channel The channel we want to write to
643      * @param bb The ByteBuffer we want to feed
644      * @param buffer The data to inject
645      * @throws IOException If the write failed
646      */
647     private void writeBuffer( FileChannel channel, ByteBuffer bb, byte[] buffer ) throws IOException
648     {
649         int size = buffer.length;
650         int pos = 0;
651 
652         // Loop until we have written all the data
653         do
654         {
655             if ( bb.remaining() >= size )
656             {
657                 // No flush, as the ByteBuffer is big enough
658                 bb.put( buffer, pos, size );
659                 size = 0;
660             }
661             else
662             {
663                 // Flush the data on disk, reinitialize the ByteBuffer
664                 int len = bb.remaining();
665                 size -= len;
666                 bb.put( buffer, pos, len );
667                 pos += len;
668 
669                 bb.flip();
670 
671                 channel.write( bb );
672 
673                 bb.clear();
674             }
675         }
676         while ( size > 0 );
677     }
678 
679 
680     /**
681      * Write a page either in the pending pages if the transaction is started,
682      * or directly on disk.
683      */
684     private PageHolder<K, V> writePage( Page<K, V> modifiedPage, long revision ) throws IOException
685     {
686         PageHolder<K, V> pageHolder = recordManager.writePage( this, modifiedPage, revision );
687 
688         return pageHolder;
689     }
690 
691 
692     /**
693      * Get the rootPzge associated to a give revision.
694      *
695      * @param revision The revision we are looking for
696      * @return The rootPage associated to this revision
697      * @throws IOException If we had an issue while accessing the underlying file
698      * @throws KeyNotFoundException If the revision does not exist for this Btree
699      */
700     public Page<K, V> getRootPage( long revision ) throws IOException, KeyNotFoundException
701     {
702         return recordManager.getRootPage( this, revision );
703     }
704 
705 
706     /**
707      * Get the current rootPage
708      *
709      * @return The rootPage
710      */
711     public Page<K, V> getRootPage()
712     {
713         return getBTreeHeader( getName() ).getRootPage();
714     }
715 
716 
717     /* no qualifier */void setRootPage( Page<K, V> root )
718     {
719         getBTreeHeader( getName() ).setRootPage( root );
720     }
721 
722 
723     /**
724      * @return the btreeInfoOffset
725      */
726     public long getBtreeInfoOffset()
727     {
728         return btreeInfoOffset;
729     }
730 
731 
732     /**
733      * @param btreeInfoOffset the btreeInfoOffset to set
734      */
735     public void setBtreeInfoOffset( long btreeInfoOffset )
736     {
737         this.btreeInfoOffset = btreeInfoOffset;
738     }
739 
740 
741     /**
742      * {@inheritDoc}
743      */
744     protected ReadTransaction<K, V> beginReadTransaction()
745     {
746         BTreeHeader<K, V> btreeHeader = getBTreeHeader( getName() );
747 
748         ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( recordManager, btreeHeader, readTransactions );
749 
750         readTransactions.add( readTransaction );
751 
752         return readTransaction;
753     }
754 
755 
756     /**
757      * {@inheritDoc}
758      */
759     protected ReadTransaction<K, V> beginReadTransaction( long revision )
760     {
761         BTreeHeader<K, V> btreeHeader = getBtreeHeader( revision );
762 
763         if ( btreeHeader != null )
764         {
765             ReadTransaction<K, V> readTransaction = new ReadTransaction<K, V>( recordManager, btreeHeader,
766                 readTransactions );
767 
768             readTransactions.add( readTransaction );
769 
770             return readTransaction;
771         }
772         else
773         {
774             return null;
775         }
776     }
777 
778 
779     /**
780      * @see Object#toString()
781      */
782     public String toString()
783     {
784         StringBuilder sb = new StringBuilder();
785 
786         sb.append( "Managed BTree" );
787         sb.append( "[" ).append( getName() ).append( "]" );
788         sb.append( "( pageSize:" ).append( getPageSize() );
789 
790         if ( getBTreeHeader( getName() ).getRootPage() != null )
791         {
792             sb.append( ", nbEntries:" ).append( getBTreeHeader( getName() ).getNbElems() );
793         }
794         else
795         {
796             sb.append( ", nbEntries:" ).append( 0 );
797         }
798 
799         sb.append( ", comparator:" );
800 
801         if ( keySerializer.getComparator() == null )
802         {
803             sb.append( "null" );
804         }
805         else
806         {
807             sb.append( keySerializer.getComparator().getClass().getSimpleName() );
808         }
809 
810         sb.append( ", DuplicatesAllowed: " ).append( isAllowDuplicates() );
811 
812         sb.append( ") : \n" );
813         sb.append( getBTreeHeader( getName() ).getRootPage().dumpPage( "" ) );
814 
815         return sb.toString();
816     }
817 }