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 }