001    /**
002     * JDBM LICENSE v1.00
003     *
004     * Redistribution and use of this software and associated documentation
005     * ("Software"), with or without modification, are permitted provided
006     * that the following conditions are met:
007     *
008     * 1. Redistributions of source code must retain copyright
009     *    statements and notices.  Redistributions must also contain a
010     *    copy of this document.
011     *
012     * 2. Redistributions in binary form must reproduce the
013     *    above copyright notice, this list of conditions and the
014     *    following disclaimer in the documentation and/or other
015     *    materials provided with the distribution.
016     *
017     * 3. The name "JDBM" must not be used to endorse or promote
018     *    products derived from this Software without prior written
019     *    permission of Cees de Groot.  For written permission,
020     *    please contact cg@cdegroot.com.
021     *
022     * 4. Products derived from this Software may not be called "JDBM"
023     *    nor may "JDBM" appear in their names without prior written
024     *    permission of Cees de Groot.
025     *
026     * 5. Due credit should be given to the JDBM Project
027     *    (http://jdbm.sourceforge.net/).
028     *
029     * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
030     * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
031     * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
032     * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
033     * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
034     * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
035     * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
036     * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
037     * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
038     * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
039     * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
040     * OF THE POSSIBILITY OF SUCH DAMAGE.
041     *
042     * Copyright 2001 (C) Alex Boisvert. All Rights Reserved.
043     * Contributions are Copyright (C) 2001 by their associated contributors.
044     *
045     */
046    
047    package jdbm.btree;
048    
049    
050    import java.io.Externalizable;
051    import java.io.IOException;
052    import java.io.ObjectInput;
053    import java.io.ObjectOutput;
054    import java.io.Serializable;
055    import java.util.Comparator;
056    
057    import org.apache.directory.server.i18n.I18n;
058    
059    import jdbm.RecordManager;
060    import jdbm.helper.Serializer;
061    import jdbm.helper.Tuple;
062    import jdbm.helper.TupleBrowser;
063    
064    
065    /**
066     * B+Tree persistent indexing data structure.  B+Trees are optimized for
067     * block-based, random I/O storage because they store multiple keys on
068     * one tree node (called <code>BPage</code>).  In addition, the leaf nodes
069     * directly contain (inline) the values associated with the keys, allowing a
070     * single (or sequential) disk read of all the values on the page.
071     * <p>
072     * B+Trees are n-airy, yeilding log(N) search cost.  They are self-balancing,
073     * preventing search performance degradation when the size of the tree grows.
074     * <p>
075     * Keys and associated values must be <code>Serializable</code> objects. The
076     * user is responsible to supply a serializable <code>Comparator</code> object
077     * to be used for the ordering of entries, which are also called <code>Tuple</code>.
078     * The B+Tree allows traversing the keys in forward and reverse order using a
079     * TupleBrowser obtained from the browse() methods.
080     * <p>
081     * This implementation does not directly support duplicate keys, but it is
082     * possible to handle duplicates by inlining or referencing an object collection
083     * as a value.
084     * <p>
085     * There is no limit on key size or value size, but it is recommended to keep
086     * both as small as possible to reduce disk I/O.   This is especially true for
087     * the key size, which impacts all non-leaf <code>BPage</code> objects.
088     *
089     * @author <a href="mailto:boisvert@intalio.com">Alex Boisvert</a>
090     * @version $Id: BTree.java,v 1.6 2005/06/25 23:12:31 doomdark Exp $
091     */
092    public class BTree implements Externalizable
093    {
094    
095        private static final boolean DEBUG = false;
096    
097        /**
098         * Version id for serialization.
099         */
100        final static long serialVersionUID = 1L;
101    
102        /**
103         * Default page size (number of entries per node)
104         */
105        public static final int DEFAULT_SIZE = 16;
106    
107        /**
108         * Page manager used to persist changes in BPages
109         */
110        protected transient RecordManager _recman;
111    
112        /**
113         * This BTree's record ID in the PageManager.
114         */
115        private transient long _recid;
116    
117        /**
118         * Comparator used to index entries.
119         */
120        protected Comparator _comparator;
121    
122        /**
123         * Serializer used to serialize index keys (optional)
124         */
125        protected Serializer _keySerializer;
126    
127        /**
128         * Serializer used to serialize index values (optional)
129         */
130        protected Serializer _valueSerializer;
131    
132        /**
133         * Height of the B+Tree.  This is the number of BPages you have to traverse
134         * to get to a leaf BPage, starting from the root.
135         */
136        private int _height;
137    
138        /**
139         * Recid of the root BPage
140         */
141        private transient long _root;
142    
143        /**
144         * Number of entries in each BPage.
145         */
146        protected int _pageSize;
147    
148        /**
149         * Total number of entries in the BTree
150         */
151        protected int _entries;
152    
153        /**
154         * Serializer used for BPages of this tree
155         */
156        private transient BPage _bpageSerializer;
157    
158    
159        /**
160         * No-argument constructor used by serialization.
161         */
162        public BTree()
163        {
164            // empty
165        }
166    
167    
168        /**
169         * Create a new persistent BTree, with 16 entries per node.
170         *
171         * @param recman Record manager used for persistence.
172         * @param comparator Comparator used to order index entries
173         */
174        public static BTree createInstance( RecordManager recman, Comparator comparator ) throws IOException
175        {
176            return createInstance( recman, comparator, null, null, DEFAULT_SIZE );
177        }
178    
179    
180        /**
181         * Create a new persistent BTree, with 16 entries per node.
182         *
183         * @param recman Record manager used for persistence.
184         * @param keySerializer Serializer used to serialize index keys (optional)
185         * @param valueSerializer Serializer used to serialize index values (optional)
186         * @param comparator Comparator used to order index entries
187         */
188        public static BTree createInstance( RecordManager recman, Comparator comparator, Serializer keySerializer,
189            Serializer valueSerializer ) throws IOException
190        {
191            return createInstance( recman, comparator, keySerializer, valueSerializer, DEFAULT_SIZE );
192        }
193    
194    
195        /**
196         * Create a new persistent BTree with the given number of entries per node.
197         *
198         * @param recman Record manager used for persistence.
199         * @param comparator Comparator used to order index entries
200         * @param keySerializer Serializer used to serialize index keys (optional)
201         * @param valueSerializer Serializer used to serialize index values (optional)
202         * @param pageSize Number of entries per page (must be even).
203         */
204        public static BTree createInstance( RecordManager recman, Comparator comparator, Serializer keySerializer,
205            Serializer valueSerializer, int pageSize ) throws IOException
206        {
207            BTree btree;
208    
209            if ( recman == null )
210            {
211                throw new IllegalArgumentException( I18n.err( I18n.ERR_517 ) );
212            }
213    
214            if ( comparator == null )
215            {
216                throw new IllegalArgumentException( I18n.err( I18n.ERR_518 ) );
217            }
218    
219            if ( !( comparator instanceof Serializable ) )
220            {
221                throw new IllegalArgumentException( I18n.err( I18n.ERR_519 ) );
222            }
223    
224            if ( keySerializer != null && !( keySerializer instanceof Serializable ) )
225            {
226                throw new IllegalArgumentException( I18n.err( I18n.ERR_520 ) );
227            }
228    
229            if ( valueSerializer != null && !( valueSerializer instanceof Serializable ) )
230            {
231                throw new IllegalArgumentException( I18n.err( I18n.ERR_521 ) );
232            }
233    
234            // make sure there's an even number of entries per BPage
235            if ( ( pageSize & 1 ) != 0 )
236            {
237                throw new IllegalArgumentException( I18n.err( I18n.ERR_522 ) );
238            }
239    
240            btree = new BTree();
241            btree._recman = recman;
242            btree._comparator = comparator;
243            btree._keySerializer = keySerializer;
244            btree._valueSerializer = valueSerializer;
245            btree._pageSize = pageSize;
246            btree._bpageSerializer = new BPage();
247            btree._bpageSerializer._btree = btree;
248            btree._recid = recman.insert( btree );
249            return btree;
250        }
251    
252    
253        /**
254         * Load a persistent BTree.
255         *
256         * @param recman RecordManager used to store the persistent btree
257         * @param recid Record id of the BTree
258         */
259        public static BTree load( RecordManager recman, long recid ) throws IOException
260        {
261            BTree btree = ( BTree ) recman.fetch( recid );
262            btree._recid = recid;
263            btree._recman = recman;
264            btree._bpageSerializer = new BPage();
265            btree._bpageSerializer._btree = btree;
266            return btree;
267        }
268    
269    
270        /**
271         * Insert an entry in the BTree.
272         * <p>
273         * The BTree cannot store duplicate entries.  An existing entry can be
274         * replaced using the <code>replace</code> flag.   If an entry with the
275         * same key already exists in the BTree, its value is returned.
276         *
277         * @param key Insert key
278         * @param value Insert value
279         * @param replace Set to true to replace an existing key-value pair.
280         * @return Existing value, if any.
281         */
282        public synchronized Object insert( Object key, Object value, boolean replace ) throws IOException
283        {
284            if ( key == null )
285            {
286                throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
287            }
288            if ( value == null )
289            {
290                throw new IllegalArgumentException( I18n.err( I18n.ERR_524 ) );
291            }
292    
293            BPage rootPage = getRoot();
294    
295            if ( rootPage == null )
296            {
297                // BTree is currently empty, create a new root BPage
298                if ( DEBUG )
299                {
300                    System.out.println( "BTree.insert() new root BPage" );
301                }
302                rootPage = new BPage( this, key, value );
303                _root = rootPage._recid;
304                _height = 1;
305                _entries = 1;
306                _recman.update( _recid, this );
307                return null;
308            }
309            else
310            {
311                BPage.InsertResult insert = rootPage.insert( _height, key, value, replace );
312                boolean dirty = false;
313                if ( insert._overflow != null )
314                {
315                    // current root page overflowed, we replace with a new root page
316                    if ( DEBUG )
317                    {
318                        System.out.println( "BTree.insert() replace root BPage due to overflow" );
319                    }
320                    rootPage = new BPage( this, rootPage, insert._overflow );
321                    _root = rootPage._recid;
322                    _height += 1;
323                    dirty = true;
324                }
325                if ( insert._existing == null )
326                {
327                    _entries++;
328                    dirty = true;
329                }
330                if ( dirty )
331                {
332                    _recman.update( _recid, this );
333                }
334                // insert might have returned an existing value
335                return insert._existing;
336            }
337        }
338    
339    
340        /**
341         * Remove an entry with the given key from the BTree.
342         *
343         * @param key Removal key
344         * @return Value associated with the key, or null if no entry with given
345         *         key existed in the BTree.
346         */
347        public synchronized Object remove( Object key ) throws IOException
348        {
349            if ( key == null )
350            {
351                throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
352            }
353    
354            BPage rootPage = getRoot();
355            if ( rootPage == null )
356            {
357                return null;
358            }
359            boolean dirty = false;
360            BPage.RemoveResult remove = rootPage.remove( _height, key );
361            if ( remove._underflow && rootPage.isEmpty() )
362            {
363                _height -= 1;
364                dirty = true;
365    
366                _recman.delete( _root );
367                if ( _height == 0 )
368                {
369                    _root = 0;
370                }
371                else
372                {
373                    _root = rootPage.childBPage( _pageSize - 1 )._recid;
374                }
375            }
376            if ( remove._value != null )
377            {
378                _entries--;
379                dirty = true;
380            }
381            if ( dirty )
382            {
383                _recman.update( _recid, this );
384            }
385            return remove._value;
386        }
387    
388    
389        /**
390         * Find the value associated with the given key.
391         *
392         * @param key Lookup key.
393         * @return Value associated with the key, or null if not found.
394         */
395        public synchronized Object find( Object key ) throws IOException
396        {
397            if ( key == null )
398            {
399                throw new IllegalArgumentException( I18n.err( I18n.ERR_523 ) );
400            }
401            BPage rootPage = getRoot();
402            if ( rootPage == null )
403            {
404                return null;
405            }
406    
407            Tuple tuple = new Tuple( null, null );
408            TupleBrowser browser = rootPage.find( _height, key );
409    
410            if ( browser.getNext( tuple ) )
411            {
412                // find returns the matching key or the next ordered key, so we must
413                // check if we have an exact match
414                if ( _comparator.compare( key, tuple.getKey() ) != 0 )
415                {
416                    return null;
417                }
418                else
419                {
420                    return tuple.getValue();
421                }
422            }
423            else
424            {
425                return null;
426            }
427        }
428    
429    
430        /**
431         * Find the value associated with the given key, or the entry immediately
432         * following this key in the ordered BTree.
433         *
434         * @param key Lookup key.
435         * @return Value associated with the key, or a greater entry, or null if no
436         *         greater entry was found.
437         */
438        public synchronized Tuple findGreaterOrEqual( Object key ) throws IOException
439        {
440            Tuple tuple;
441            TupleBrowser browser;
442    
443            if ( key == null )
444            {
445                // there can't be a key greater than or equal to "null"
446                // because null is considered an infinite key.
447                return null;
448            }
449    
450            tuple = new Tuple( null, null );
451            browser = browse( key );
452            if ( browser.getNext( tuple ) )
453            {
454                return tuple;
455            }
456            else
457            {
458                return null;
459            }
460        }
461    
462    
463        /**
464         * Get a browser initially positioned at the beginning of the BTree.
465         * <p><b>
466         * WARNING: ???If you make structural modifications to the BTree during
467         * browsing, you will get inconsistent browing results.
468         * </b>
469         *
470         * @return Browser positionned at the beginning of the BTree.
471         */
472        public synchronized TupleBrowser browse() throws IOException
473        {
474            BPage rootPage = getRoot();
475            if ( rootPage == null )
476            {
477                return EmptyBrowser.INSTANCE;
478            }
479            TupleBrowser browser = rootPage.findFirst();
480            return browser;
481        }
482    
483    
484        /**
485         * Get a browser initially positioned just before the given key.
486         * <p><b>
487         * WARNING: ???If you make structural modifications to the BTree during
488         * browsing, you will get inconsistent browing results.
489         * </b>
490         *
491         * @param key Key used to position the browser.  If null, the browser
492         *            will be positionned after the last entry of the BTree.
493         *            (Null is considered to be an "infinite" key)
494         * @return Browser positionned just before the given key.
495         */
496        public synchronized TupleBrowser browse( Object key ) throws IOException
497        {
498            BPage rootPage = getRoot();
499            if ( rootPage == null )
500            {
501                return EmptyBrowser.INSTANCE;
502            }
503            TupleBrowser browser = rootPage.find( _height, key );
504            return browser;
505        }
506    
507    
508        /**
509         * Return the number of entries (size) of the BTree.
510         */
511        public synchronized int size()
512        {
513            return _entries;
514        }
515    
516    
517        /**
518         * Return the persistent record identifier of the BTree.
519         */
520        public long getRecid()
521        {
522            return _recid;
523        }
524    
525    
526        /**
527         * Return the root BPage, or null if it doesn't exist.
528         */
529        private BPage getRoot() throws IOException
530        {
531            if ( _root == 0 )
532            {
533                return null;
534            }
535            BPage root = ( BPage ) _recman.fetch( _root, _bpageSerializer );
536            root._recid = _root;
537            root._btree = this;
538            return root;
539        }
540    
541    
542        /**
543         * Implement Externalizable interface.
544         */
545        public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException
546        {
547            _comparator = ( Comparator ) in.readObject();
548            _keySerializer = ( Serializer ) in.readObject();
549            _valueSerializer = ( Serializer ) in.readObject();
550            _height = in.readInt();
551            _root = in.readLong();
552            _pageSize = in.readInt();
553            _entries = in.readInt();
554        }
555    
556    
557        /**
558         * Implement Externalizable interface.
559         */
560        public void writeExternal( ObjectOutput out ) throws IOException
561        {
562            out.writeObject( _comparator );
563            out.writeObject( _keySerializer );
564            out.writeObject( _valueSerializer );
565            out.writeInt( _height );
566            out.writeLong( _root );
567            out.writeInt( _pageSize );
568            out.writeInt( _entries );
569        }
570    
571    
572        public void setValueSerializer( Serializer valueSerializer )
573        {
574            _valueSerializer = valueSerializer;
575        }
576    
577        /*
578        public void assert() throws IOException {
579            BPage root = getRoot();
580            if ( root != null ) {
581                root.assertRecursive( _height );
582            }
583        }
584        */
585    
586        /*
587        public void dump() throws IOException {
588            BPage root = getRoot();
589            if ( root != null ) {
590                root.dumpRecursive( _height, 0 );
591            }
592        }
593        */
594    
595        /** PRIVATE INNER CLASS
596         *  Browser returning no element.
597         */
598        static class EmptyBrowser extends TupleBrowser
599        {
600    
601            static TupleBrowser INSTANCE = new EmptyBrowser();
602    
603    
604            public boolean getNext( Tuple tuple )
605            {
606                return false;
607            }
608    
609    
610            public boolean getPrevious( Tuple tuple )
611            {
612                return false;
613            }
614        }
615    
616    
617        /**
618         * @return the _comparator
619         */
620        public Comparator getComparator()
621        {
622            return _comparator;
623        }
624    }