Java > Open Source Codes > com > caucho > db > index > BTree


1 /*
2  * Copyright (c) 1998-2006 Caucho Technology -- all rights reserved
3  *
4  * This file is part of Resin(R) Open Source
5  *
6  * Each copy or derived work must preserve the copyright notice and this
7  * notice unmodified.
8  *
9  * Resin Open Source is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation; either version 2 of the License, or
12  * (at your option) any later version.
13  *
14  * Resin Open Source is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE, or any warranty
17  * of NON-INFRINGEMENT. See the GNU General Public License for more
18  * details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with Resin Open Source; if not, write to the
22  *
23  * Free Software Foundation, Inc.
24  * 59 Temple Place, Suite 330
25  * Boston, MA 02111-1307 USA
26  *
27  * @author Scott Ferguson
28  */
29
30 package com.caucho.db.index;
31
32 import com.caucho.db.Database;
33 import com.caucho.db.store.Block;
34 import com.caucho.db.store.BlockManager;
35 import com.caucho.db.store.Lock;
36 import com.caucho.db.store.Store;
37 import com.caucho.db.store.Transaction;
38 import com.caucho.log.Log;
39 import com.caucho.sql.SQLExceptionWrapper;
40 import com.caucho.util.L10N;
41 import com.caucho.vfs.Path;
42
43 import java.io.IOException ;
44 import java.sql.SQLException ;
45 import java.util.ArrayList ;
46 import java.util.logging.Level ;
47 import java.util.logging.Logger ;
48
49 /**
50  * Structure of the table:
51  *
52  * <pre>
53  * b4 - flags
54  * b4 - length
55  * b8 - parent
56  * b8 - next
57  * tuples*
58  * </pre>
59  *
60  * Structure of a tuple:
61  *
62  * <pre>
63  * b8 - ptr to the actual data
64  * key - the tuple's key
65  * </pre>
66  */
67 public final class BTree {
68   private final static L10N L = new L10N(BTree.class);
69   private final static Logger log = Log.open(BTree.class);
70   
71   public final static long FAIL = 0;
72   private final static int BLOCK_SIZE = Store.BLOCK_SIZE;
73   private final static int PTR_SIZE = 8;
74
75   private final static int FLAGS_OFFSET = 0;
76   private final static int LENGTH_OFFSET = FLAGS_OFFSET + 4;
77   private final static int PARENT_OFFSET = LENGTH_OFFSET + 4;
78   private final static int NEXT_OFFSET = PARENT_OFFSET + PTR_SIZE;
79   private final static int HEADER_SIZE = NEXT_OFFSET + PTR_SIZE;
80
81   private final static int LEAF_FLAG = 1;
82
83   private BlockManager _blockManager;
84
85   private final Lock _lock;
86   private Store _store;
87   private long _rootBlockId;
88   private int _keySize;
89   private int _tupleSize;
90   private int _n;
91   private int _minN;
92   
93   private KeyCompare _keyCompare;
94
95   private int _blockCount;
96
97   private volatile boolean _isStarted;
98
99   /**
100    * Creates a new BTree with the given backing.
101    *
102    * @param store the underlying store containing the btree.
103    */
104   public BTree(Store store,
105            long rootBlockId,
106            int keySize,
107            KeyCompare keyCompare)
108     throws IOException
109   {
110     if (keyCompare == null)
111       throw new NullPointerException ();
112     
113     _store = store;
114     _blockManager = _store.getBlockManager();
115     _rootBlockId = rootBlockId;
116     _lock = new Lock("index:" + store.getName());
117     
118     if (BLOCK_SIZE < keySize + HEADER_SIZE)
119       throw new IOException (L.l("BTree key size `{0}' is too large.",
120                                 keySize));
121
122     _keySize = keySize;
123
124     _tupleSize = keySize + PTR_SIZE;
125
126     _n = (BLOCK_SIZE - HEADER_SIZE) / _tupleSize;
127     _minN = (_n + 1) / 2;
128     if (_minN < 0)
129       _minN = 1;
130
131     _keyCompare = keyCompare;
132   }
133
134   /**
135    * Returns the index root.
136    */
137   public long getIndexRoot()
138   {
139     return _rootBlockId;
140   }
141
142   /**
143    * Creates and initializes the btree.
144    */
145   public void create()
146     throws IOException
147   {
148   }
149
150   /**
151    * Looks up the block for the given key in the btree, returning
152    * BTree.FAIL for a failed lookup.
153    */
154   /*
155   public long lookup(byte []keyBuffer,
156              int keyOffset,
157              int keyLength,
158              Transaction xa)
159     throws IOException, SQLException
160   {
161     xa.lockRead(_lock);
162
163     try {
164       long blockId = _rootBlockId;
165
166       while (blockId != 0) {
167     Block block = _store.readBlock(blockId);
168     boolean isLeaf = true;
169     long value;
170       
171     try {
172       byte []buffer = block.getBuffer();
173
174       isLeaf = isLeaf(buffer);
175       
176       value = lookupTuple(blockId, buffer,
177                   keyBuffer, keyOffset, keyLength,
178                   isLeaf);
179     } finally {
180       block.free();
181     }
182
183     if (isLeaf || value == FAIL)
184       return value;
185
186     blockId = value;
187       }
188     } finally {
189       xa.unlockRead(_lock);
190     }
191
192     return FAIL;
193   }
194   */
195   
196   public long lookup(byte []keyBuffer,
197              int keyOffset,
198              int keyLength,
199              Transaction xa)
200     throws IOException , SQLException
201   {
202     return lookup(keyBuffer, keyOffset, keyLength, xa, _rootBlockId);
203   }
204   
205   private long lookup(byte []keyBuffer,
206              int keyOffset,
207              int keyLength,
208              Transaction xa,
209              long blockId)
210     throws IOException , SQLException
211   {
212     Block block = _store.readBlock(blockId);
213
214     try {
215       xa.lockRead(block.getLock());
216
217       try {
218     byte []buffer = block.getBuffer();
219
220     boolean isLeaf = isLeaf(buffer);
221       
222     long value = lookupTuple(blockId, buffer,
223                  keyBuffer, keyOffset, keyLength,
224                  isLeaf);
225
226     if (isLeaf || value == FAIL)
227       return value;
228     else
229       return lookup(keyBuffer, keyOffset, keyLength,
230             xa, value);
231       } finally {
232         xa.unlockRead(block.getLock());
233       }
234     } finally {
235       block.free();
236     }
237   }
238
239   /**
240    * Inserts the new value for the given key.
241    */
242   /*
243   public void insert(byte []keyBuffer,
244              int keyOffset,
245              int keyLength,
246              long value,
247              Transaction xa,
248              boolean isOverride)
249     throws SQLException
250   {
251     xa.lockWrite(_lock);
252     
253     try {
254       if (value == FAIL)
255     throw new IllegalArgumentException();
256     
257       long blockId = _rootBlockId;
258       long parentBlockId = 0;
259     
260       while (blockId != 0) {
261     Block block = _store.readBlock(blockId);
262
263     try {
264       byte []buffer = block.getBuffer();
265
266       boolean isLeaf = isLeaf(buffer);
267
268       int length = getLength(buffer);
269
270       if (length == _n) {
271         if (blockId == _rootBlockId) {
272           splitRoot(block, xa);
273
274           continue;
275         }
276         else {
277           split(parentBlockId, block, xa);
278         
279           blockId = _rootBlockId;
280           parentBlockId = 0;
281
282           continue;
283         }
284       }
285
286       if (isLeaf) {
287         block.setFlushDirtyOnCommit(false);
288         block.setDirty(0, Store.BLOCK_SIZE);
289         
290         insertLeafBlock(blockId, buffer,
291                 keyBuffer, keyOffset, keyLength,
292                 value,
293                 isOverride);
294
295         return;
296       }
297       else {
298         parentBlockId = blockId;
299         blockId = lookupTuple(blockId, buffer,
300                   keyBuffer, keyOffset, keyLength,
301                   isLeaf);
302       }
303     } finally {
304       block.free();
305     }
306       }
307     } catch (IOException e) {
308       throw new SQLExceptionWrapper(e);
309     } finally {
310       xa.unlockWrite(_lock);
311     }
312   }
313   */
314   
315   /**
316    * Inserts the new value for the given key.
317    *
318    * @return false if the block needs to be split
319    */
320   public void insert(byte []keyBuffer,
321              int keyOffset,
322              int keyLength,
323              long value,
324              Transaction xa,
325              boolean isOverride)
326     throws SQLException
327   {
328     try {
329       while (! insert(keyBuffer, keyOffset, keyLength,
330               value, xa, isOverride,
331               _rootBlockId)) {
332     splitRoot(_rootBlockId, xa);
333       }
334     } catch (IOException e) {
335       log.log(Level.FINE, e.toString(), e);
336       
337       throw new SQLException (e.toString());
338     }
339   }
340
341   /**
342    * Inserts the new value for the given key.
343    *
344    * @return false if the block needs to be split
345    */
346   private boolean insert(byte []keyBuffer,
347              int keyOffset,
348              int keyLength,
349              long value,
350              Transaction xa,
351              boolean isOverride,
352              long blockId)
353     throws IOException , SQLException
354   {
355     Block block = _store.readBlock(blockId);
356     try {
357       xa.lockRead(block.getLock());
358       
359       try {
360     byte []buffer = block.getBuffer();
361
362     int length = getLength(buffer);
363
364     if (length == _n) {
365       // return false if the block needs to be split
366 return false;
367     }
368     
369     if (isLeaf(buffer)) {
370       insertValue(keyBuffer, keyOffset, keyLength,
371               value, xa, isOverride, block);
372
373       return true;
374     }
375
376     long childBlockId = lookupTuple(blockId, buffer,
377                     keyBuffer, keyOffset, keyLength,
378                     false);
379
380     while (! insert(keyBuffer, keyOffset, keyLength,
381             value, xa, isOverride,
382             childBlockId)) {
383       split(block, childBlockId, xa);
384
385       childBlockId = lookupTuple(blockId, buffer,
386                      keyBuffer, keyOffset, keyLength,
387                      false);
388     }
389
390     return true;
391       } finally {
392     xa.unlockRead(block.getLock());
393       }
394     } finally {
395       block.free();
396     }
397   }
398     
399   /**
400    * Inserts into the next block given the current block and the given key.
401    */
402   private void insertValue(byte []keyBuffer,
403                int keyOffset,
404                int keyLength,
405                long value,
406                Transaction xa,
407                boolean isOverride,
408                Block block)
409     throws IOException , SQLException
410   {
411     byte []buffer = block.getBuffer();
412         
413     xa.lockWrite(block.getLock());
414     try {
415       block.setFlushDirtyOnCommit(false);
416       block.setDirty(0, Store.BLOCK_SIZE);
417         
418       insertLeafBlock(block.getBlockId(), buffer,
419               keyBuffer, keyOffset, keyLength,
420               value,
421               isOverride);
422     } finally {
423       xa.unlockWrite(block.getLock());
424     }
425   }
426
427   /**
428    * Inserts into the next block given the current block and the given key.
429    */
430   private long insertLeafBlock(long blockId,
431                                byte []buffer,
432                                byte []keyBuffer,
433                                int keyOffset,
434                                int keyLength,
435                                long value,
436                    boolean isOverride)
437     throws IOException , SQLException
438   {
439     int offset = HEADER_SIZE;
440     int tupleSize = _tupleSize;
441     int length = getLength(buffer);
442
443     for (int i = 0; i < length; i++) {
444       int cmp = _keyCompare.compare(keyBuffer, keyOffset,
445                     buffer, offset + PTR_SIZE,
446                     keyLength);
447
448       if (0 < cmp) {
449         offset += tupleSize;
450         continue;
451       }
452       else if (cmp == 0) {
453     if (! isOverride) {
454       long oldValue = getPointer(buffer, offset);
455
456       if (value != oldValue)
457         throw new SQLException (L.l("BTree insert of mismatched value"));
458     }
459     
460         setPointer(buffer, offset, value);
461         //writeBlock(blockIndex, block);
462
463         return 0;
464       }
465       else if (length < _n) {
466         return addKey(blockId, buffer, offset, i, length,
467                       keyBuffer, keyOffset, keyLength, value);
468       }
469       else {
470     throw new IllegalStateException ("ran out of key space");
471       }
472     }
473
474     if (length < _n) {
475       return addKey(blockId, buffer, offset, length, length,
476                     keyBuffer, keyOffset, keyLength, value);
477     }
478
479     throw new IllegalStateException ();
480
481     // return split(blockIndex, block);
482 }
483
484   private long addKey(long blockId, byte []buffer, int offset,
485               int index, int length,
486                       byte []keyBuffer, int keyOffset, int keyLength,
487                       long value)
488     throws IOException
489   {
490     int tupleSize = _tupleSize;
491
492     if (index < length) {
493       System.arraycopy(buffer, offset,
494                        buffer, offset + tupleSize,
495                        (length - index) * tupleSize);
496     }
497     
498     setPointer(buffer, offset, value);
499     setLength(buffer, length + 1);
500
501     if (log.isLoggable(Level.FINER))
502       log.finer("btree insert at " + debugId(blockId) + ":" + offset + " value:" + debugId(value));
503
504     System.arraycopy(keyBuffer, keyOffset,
505              buffer, offset + PTR_SIZE,
506              keyLength);
507           
508     for (int j = PTR_SIZE + keyLength; j < tupleSize; j++)
509       buffer[offset + j] = 0;
510
511     return -value;
512   }
513
514   /**
515    * The length in lBuf is assumed to be the length of the buffer.
516    */
517   private void split(Block parent,
518              long blockId,
519              Transaction xa)
520     throws IOException , SQLException
521   {
522     xa.lockWrite(parent.getLock());
523     
524     try {
525       Block block = _store.readBlock(blockId);
526
527       try {
528     xa.lockReadAndWrite(block.getLock());
529     
530     try {
531       split(parent, block, xa);
532     } finally {
533       xa.unlockReadAndWrite(block.getLock());
534     }
535       } finally {
536     block.free();
537       }
538     } finally {
539       xa.unlockWrite(parent.getLock());
540     }
541   }
542
543   /**
544    * The length in lBuf is assumed to be the length of the buffer.
545    */
546   private void split(Block parentBlock,
547              Block block,
548              Transaction xa)
549     throws IOException , SQLException
550   {
551     long parentId = parentBlock.getBlockId();
552     long blockId = block.getBlockId();
553     
554     log.finer("btree splitting " + debugId(blockId));
555     
556     block.setFlushDirtyOnCommit(false);
557     block.setDirty(0, Store.BLOCK_SIZE);
558
559     byte []buffer = block.getBuffer();
560     int length = getLength(buffer);
561       
562     //System.out.println("INDEX SPLIT: " + debugId(blockId) + " " + length + " " + block + " " + buffer);
563
564     Block leftBlock = null;
565
566     try {
567       parentBlock.setFlushDirtyOnCommit(false);
568       parentBlock.setDirty(0, Store.BLOCK_SIZE);
569     
570       byte []parentBuffer = parentBlock.getBuffer();
571       int parentLength = getLength(parentBuffer);
572     
573       leftBlock = _store.allocateIndexBlock();
574       leftBlock.setFlushDirtyOnCommit(false);
575       leftBlock.setDirty(0, Store.BLOCK_SIZE);
576       
577       byte []leftBuffer = leftBlock.getBuffer();
578       long leftBlockId = leftBlock.getBlockId();
579
580       int pivot = length / 2;
581
582       int pivotSize = pivot * _tupleSize;
583       int pivotEnd = HEADER_SIZE + pivotSize;
584
585       System.arraycopy(buffer, HEADER_SIZE,
586                leftBuffer, HEADER_SIZE,
587                pivotSize);
588
589       setInt(leftBuffer, FLAGS_OFFSET, getInt(buffer, FLAGS_OFFSET));
590       setLength(leftBuffer, pivot);
591       // XXX: NEXT_OFFSET needs to work with getRightIndex
592 setPointer(leftBuffer, NEXT_OFFSET, 0);
593       setPointer(leftBuffer, PARENT_OFFSET, parentId);
594
595       System.arraycopy(buffer, pivotEnd,
596                buffer, HEADER_SIZE,
597                length * _tupleSize - pivotEnd);
598
599       setLength(buffer, length - pivot);
600
601       insertLeafBlock(parentId, parentBuffer,
602               leftBuffer, pivotEnd - _tupleSize + PTR_SIZE, _keySize,
603               leftBlockId,
604               true);
605     } finally {
606       if (leftBlock != null)
607     leftBlock.free();
608     }
609   }
610
611   /**
612    * The length in lBuf is assumed to be the length of the buffer.
613    */
614   private void splitRoot(long rootBlockId,
615              Transaction xa)
616     throws IOException , SQLException
617   {
618     Block rootBlock = _store.readBlock(rootBlockId);
619
620     try {
621       xa.lockReadAndWrite(rootBlock.getLock());
622       
623       try {
624     splitRoot(rootBlock, xa);
625       } finally {
626     xa.unlockReadAndWrite(rootBlock.getLock());
627       }
628     } finally {
629       rootBlock.free();
630     }
631   }
632
633   /**
634    * Splits the current leaf into two. Half of the entries go to the
635    * left leaf and half go to the right leaf.
636    */
637   private void splitRoot(Block parentBlock, Transaction xa)
638     throws IOException
639   {
640     long parentId = parentBlock.getBlockId();
641     
642     //System.out.println("INDEX SPLIT ROOT: " + (parentId / BLOCK_SIZE));
643 log.finer("btree splitting root " + (parentId / BLOCK_SIZE));
644
645     Block leftBlock = null;
646     Block rightBlock = null;
647
648     try {
649       parentBlock.setFlushDirtyOnCommit(false);
650       parentBlock.setDirty(0, Store.BLOCK_SIZE);
651
652       byte []parentBuffer = parentBlock.getBuffer();
653
654       int parentFlags = getInt(parentBuffer, FLAGS_OFFSET);
655
656       leftBlock = _store.allocateIndexBlock();
657       leftBlock.setFlushDirtyOnCommit(false);
658       leftBlock.setDirty(0, Store.BLOCK_SIZE);
659       
660       long leftBlockId = leftBlock.getBlockId();
661     
662       rightBlock = _store.allocateIndexBlock();
663       rightBlock.setFlushDirtyOnCommit(false);
664       rightBlock.setDirty(0, Store.BLOCK_SIZE);
665       
666       long rightBlockId = rightBlock.getBlockId();
667
668       int length = getLength(parentBuffer);
669
670       int pivot = (length - 1) / 2;
671
672       int pivotOffset = HEADER_SIZE + pivot * _tupleSize;
673       long pivotValue = getPointer(parentBuffer, pivotOffset);
674
675       byte []leftBuffer = leftBlock.getBuffer();
676
677       System.arraycopy(parentBuffer, HEADER_SIZE,
678                leftBuffer, HEADER_SIZE,
679                pivotOffset + _tupleSize - HEADER_SIZE);
680
681       setInt(leftBuffer, FLAGS_OFFSET, parentFlags);
682       setLength(leftBuffer, pivot + 1);
683       setPointer(leftBuffer, PARENT_OFFSET, parentId);
684       setPointer(leftBuffer, NEXT_OFFSET, rightBlockId);
685
686       byte []rightBuffer = rightBlock.getBuffer();
687
688       System.arraycopy(parentBuffer, pivotOffset + _tupleSize,
689                rightBuffer, HEADER_SIZE,
690                (length - pivot - 1) * _tupleSize);
691
692       setInt(rightBuffer, FLAGS_OFFSET, parentFlags);
693       setLength(rightBuffer, length - pivot - 1);
694       setPointer(rightBuffer, PARENT_OFFSET, parentId);
695       setPointer(rightBuffer, NEXT_OFFSET,
696          getPointer(parentBuffer, NEXT_OFFSET));
697
698       System.arraycopy(parentBuffer, pivotOffset,
699                parentBuffer, HEADER_SIZE,
700                _tupleSize);
701       setPointer(parentBuffer, HEADER_SIZE, leftBlockId);
702
703       setInt(parentBuffer, FLAGS_OFFSET, LEAF_FLAG);
704       setLength(parentBuffer, 1);
705       setPointer(parentBuffer, NEXT_OFFSET, rightBlockId);
706     } finally {
707       if (leftBlock != null)
708     leftBlock.free();
709       
710       if (rightBlock != null)
711     rightBlock.free();
712     }
713   }
714
715   /**
716    * Inserts the new value for the given key.
717    */
718   /*
719   public void remove(byte []keyBuffer,
720              int keyOffset,
721              int keyLength,
722              Transaction xa)
723     throws SQLException
724   {
725     xa.lockWrite(_lock);
726
727     try {
728       remove(-1, _rootBlockId, keyBuffer, keyOffset, keyLength, xa);
729     } catch (IOException e) {
730       throw new SQLExceptionWrapper(e);
731     } finally {
732       xa.unlockWrite(_lock);
733     }
734   }
735   */
736
737   /**
738    * Inserts the new value for the given key.
739    */
740   /*
741   private void remove(long parentId,
742               long blockId,
743               byte []keyBuffer,
744               int keyOffset,
745               int keyLength,
746               Transaction xa)
747     throws IOException
748   {
749     Block block = _store.readBlock(blockId);
750
751     try {
752       byte []buffer = block.getBuffer();
753
754       boolean isLeaf = isLeaf(buffer);
755       
756       if (isLeaf) {
757     block.setFlushDirtyOnCommit(false);
758     block.setDirty(0, Store.BLOCK_SIZE);
759
760     removeLeafEntry(blockId, buffer,
761             keyBuffer, keyOffset, keyLength);
762       }
763       else {
764     long childId;
765     
766     childId = lookupTuple(blockId, buffer,
767                   keyBuffer, keyOffset, keyLength,
768                   isLeaf);
769
770     if (childId == 0)
771       return;
772
773     remove(blockId, childId,
774            keyBuffer, keyOffset, keyLength,
775            xa);
776       }
777
778       if (joinBlocks(parentId, blockId, buffer, xa)) {
779     xa.deallocateBlock(block);
780       }
781     } finally {
782       block.free();
783     }
784   }
785   */
786   
787   public void remove(byte []keyBuffer,
788               int keyOffset,
789               int keyLength,
790               Transaction xa)
791     throws SQLException
792   {
793     try {
794       Block rootBlock = _store.readBlock(_rootBlockId);
795
796       try {
797     xa.lockRead(rootBlock.getLock());
798
799     try {
800       remove(rootBlock, keyBuffer, keyOffset, keyLength, xa);
801     } finally {
802       xa.unlockRead(rootBlock.getLock());
803     }
804       } finally {
805     rootBlock.free();
806       }
807     } catch (IOException e) {
808       throw new SQLExceptionWrapper(e);
809     }
810   }
811   
812   private boolean remove(Block block,
813              byte []keyBuffer,
814              int keyOffset,
815              int keyLength,
816              Transaction xa)
817     throws IOException , SQLException
818   {
819     byte []buffer = block.getBuffer();
820     long blockId = block.getBlockId();
821
822     boolean isLeaf = isLeaf(buffer);
823       
824     if (isLeaf) {
825       xa.lockWrite(block.getLock());
826
827       try {
828     block.setFlushDirtyOnCommit(false);
829     block.setDirty(0, Store.BLOCK_SIZE);
830
831     removeLeafEntry(blockId, buffer,
832             keyBuffer, keyOffset, keyLength);
833       } finally {
834     xa.unlockWrite(block.getLock());
835       }
836     }
837     else {
838       long childId;
839     
840       childId = lookupTuple(blockId, buffer,
841                 keyBuffer, keyOffset, keyLength,
842                 isLeaf);
843
844       if (childId == FAIL)
845     return true;
846
847       Block childBlock = _store.readBlock(childId);
848       try {
849     boolean isJoin = false;
850     
851     xa.lockRead(childBlock.getLock());
852
853     try {
854       isJoin = ! remove(childBlock,
855                 keyBuffer, keyOffset, keyLength,
856                 xa);
857     } finally {
858       xa.unlockRead(childBlock.getLock());
859     }
860
861     if (isJoin) {
862       if (joinBlocks(block, childBlock, xa)) {
863         xa.deallocateBlock(childBlock);
864       }
865     }
866       } finally {
867     childBlock.free();
868       }
869     }
870       
871     return _minN <= getLength(buffer);
872   }
873
874   /**
875    * Performs any block-merging cleanup after the delete.
876    *
877    * @return true if the block should be deleted/freed
878    */
879   private boolean joinBlocks(Block parent,
880                  Block block,
881                  Transaction xa)
882     throws IOException , SQLException
883   {
884     byte []parentBuffer = parent.getBuffer();
885     int parentLength = getLength(parentBuffer);
886
887     long blockId = block.getBlockId();
888     byte []buffer = block.getBuffer();
889     int length = getLength(buffer);
890     
891     //System.out.println("INDEX JOIN: " + debugId(blockId));
892
893     xa.lockWrite(parent.getLock());
894     try {
895       long leftBlockId = getLeftBlockId(parent, blockId);
896       long rightBlockId = getRightBlockId(parent, blockId);
897
898       // try to shift from left and right first
899 if (leftBlockId > 0) {
900     Block leftBlock = _store.readBlock(leftBlockId);
901
902     try {
903       byte []leftBuffer = leftBlock.getBuffer();
904     
905       int leftLength = getLength(leftBuffer);
906
907       if (_minN < leftLength && isLeaf(buffer) == isLeaf(leftBuffer)) {
908         xa.lockReadAndWrite(leftBlock.getLock());
909       
910         try {
911           xa.lockReadAndWrite(block.getLock());
912         
913           try {
914         parent.setFlushDirtyOnCommit(false);
915         parent.setDirty(0, Store.BLOCK_SIZE);
916         
917         leftBlock.setFlushDirtyOnCommit(false);
918         leftBlock.setDirty(0, Store.BLOCK_SIZE);
919       
920         //System.out.println("MOVE_FROM_LEFT: " + debugId(blockId) + " from " + debugId(leftBlockId));
921 moveFromLeft(parentBuffer, leftBuffer, buffer, blockId);
922
923         return false;
924           } finally {
925         xa.unlockReadAndWrite(block.getLock());
926           }
927         } finally {
928           xa.unlockReadAndWrite(leftBlock.getLock());
929         }
930       }
931     } finally {
932       leftBlock.free();
933     }
934       }
935
936       if (rightBlockId > 0) {
937     Block rightBlock = _store.readBlock(rightBlockId);
938
939     try {
940       byte []rightBuffer = rightBlock.getBuffer();
941     
942       int rightLength = getLength(rightBuffer);
943       
944       if (_minN < rightLength & isLeaf(buffer) == isLeaf(rightBuffer)) {
945         xa.lockReadAndWrite(block.getLock());
946
947         try {
948           xa.lockReadAndWrite(rightBlock.getLock());
949
950           try {
951         parent.setFlushDirtyOnCommit(false);
952         parent.setDirty(0, Store.BLOCK_SIZE);
953         
954         rightBlock.setFlushDirtyOnCommit(false);
955         rightBlock.setDirty(0, Store.BLOCK_SIZE);
956
957         //System.out.println("MOVE_FROM_RIGHT: " + debugId(blockId) + " from " + debugId(rightBlockId));
958
959         moveFromRight(parentBuffer, buffer, rightBuffer, blockId);
960
961         return false;
962           } finally {
963         xa.unlockReadAndWrite(rightBlock.getLock());
964           }
965         } finally {
966           xa.unlockReadAndWrite(block.getLock());
967         }
968       }
969     } finally {
970       rightBlock.free();
971     }
972       }
973
974       if (parentLength < 2)
975     return false;
976     
977       if (leftBlockId > 0) {
978     Block leftBlock = _store.readBlock(leftBlockId);
979       
980     try {
981       byte []leftBuffer = leftBlock.getBuffer();
982       int leftLength = getLength(leftBuffer);
983       
984       if (isLeaf(leftBuffer) == isLeaf(buffer)
985           && length + leftLength <= _n) {
986         xa.lockReadAndWrite(leftBlock.getLock());
987
988         try {
989           xa.lockReadAndWrite(block.getLock());
990
991           try {
992         parent.setFlushDirtyOnCommit(false);
993         parent.setDirty(0, Store.BLOCK_SIZE);
994       
995         leftBlock.setFlushDirtyOnCommit(false);
996         leftBlock.setDirty(0, Store.BLOCK_SIZE);
997       
998         //System.out.println("MERGE_LEFT: " + debugId(blockId) + " from " + debugId(leftBlockId));
999
1000        mergeLeft(parentBuffer, leftBuffer, buffer, blockId);
1001
1002        return true;
1003          } finally {
1004        xa.unlockReadAndWrite(block.getLock());
1005          }
1006        } finally {
1007          xa.unlockReadAndWrite(leftBlock.getLock());
1008        }
1009      }
1010    } finally {
1011      leftBlock.free();
1012    }
1013      }
1014    
1015      if (rightBlockId > 0) {
1016    Block rightBlock = _store.readBlock(rightBlockId);
1017
1018    try {
1019      byte []rightBuffer = rightBlock.getBuffer();
1020      int rightLength = getLength(rightBuffer);
1021
1022      if (isLeaf(rightBuffer) == isLeaf(buffer)
1023          && length + rightLength <= _n) {
1024        xa.lockReadAndWrite(block.getLock());
1025
1026        try {
1027          xa.lockReadAndWrite(rightBlock.getLock());
1028
1029          try {
1030        rightBlock.setFlushDirtyOnCommit(false);
1031        rightBlock.setDirty(0, Store.BLOCK_SIZE);
1032      
1033        parent.setFlushDirtyOnCommit(false);
1034        parent.setDirty(0, Store.BLOCK_SIZE);
1035      
1036        //System.out.println("MERGE_RIGHT: " + debugId(blockId) + " from " + debugId(rightBlockId));
1037
1038        mergeRight(parentBuffer, buffer, rightBuffer, blockId);
1039
1040        return true;
1041          } finally {
1042        xa.unlockReadAndWrite(rightBlock.getLock());
1043          }
1044        } finally {
1045          xa.unlockReadAndWrite(block.getLock());
1046        }
1047      }
1048    } finally {
1049      rightBlock.free();
1050    }
1051      }
1052
1053      return false;
1054    } finally {
1055      xa.unlockWrite(parent.getLock());
1056    }
1057  }
1058
1059  /**
1060   * Returns the index to the left of the current one
1061   */
1062  private long getLeftBlockId(Block parent, long blockId)
1063  {
1064    byte []buffer = parent.getBuffer();
1065    
1066    int length = getLength(buffer);
1067
1068    int offset = HEADER_SIZE;
1069    int tupleSize = _tupleSize;
1070    int end = offset + length * tupleSize;
1071
1072    for (; offset < end; offset += tupleSize) {
1073      long pointer = getPointer(buffer, offset);
1074
1075      if (pointer == blockId) {
1076    if (HEADER_SIZE < offset) {
1077      return getPointer(buffer, offset - tupleSize);
1078    }
1079    else
1080      return -1;
1081      }
1082    }
1083    
1084    long pointer = getPointer(buffer, NEXT_OFFSET);
1085    
1086    if (pointer == blockId)
1087      return getPointer(buffer, HEADER_SIZE + (length - 1) * tupleSize);
1088    else
1089      throw new IllegalStateException ("Can't find " + debugId(blockId) + " in parent " + debugId(parent.getBlockId()));
1090  }
1091
1092  /**
1093   * Takes the last entry from the left block and moves it to the
1094   * first entry in the current block.
1095   *
1096   * @param parentBuffer the parent block buffer
1097   * @param leftBuffer the left block buffer
1098   * @param buffer the block's buffer
1099   * @param index the index of the block
1100   */
1101  private void moveFromLeft(byte []parentBuffer,
1102                byte []leftBuffer,
1103                byte []buffer,
1104                long blockId)
1105  {
1106    int parentLength = getLength(parentBuffer);
1107
1108    int tupleSize = _tupleSize;
1109    int parentOffset = HEADER_SIZE;
1110    int parentEnd = parentOffset + parentLength * tupleSize;
1111
1112    int leftLength = getLength(leftBuffer);
1113
1114    int length = getLength(buffer);
1115
1116    // pointer in the parent to the left defaults to the tail - 1
1117 int parentLeftOffset = -1;
1118
1119    if (blockId == getPointer(parentBuffer, NEXT_OFFSET)) {
1120      // parentLeftOffset = parentOffset - tupleSize;
1121 parentLeftOffset = parentEnd - tupleSize;
1122    }
1123    else {
1124      for (parentOffset += tupleSize;
1125       parentOffset < parentEnd;
1126       parentOffset += tupleSize) {
1127    long pointer = getPointer(parentBuffer, parentOffset);
1128
1129    if (pointer == blockId) {
1130      parentLeftOffset = parentOffset - tupleSize;
1131      break;
1132    }
1133      }
1134    }
1135
1136    if (parentLeftOffset < 0) {
1137      log.warning("Can't find parent left in deletion borrow left ");
1138      return;
1139    }
1140
1141    // shift the data in the buffer
1142 System.arraycopy(buffer, HEADER_SIZE,
1143             buffer, HEADER_SIZE + tupleSize,
1144             length * tupleSize);
1145
1146    // copy the last item in the left to the buffer
1147 System.arraycopy(leftBuffer, HEADER_SIZE + (leftLength - 1) * tupleSize,
1148             buffer, HEADER_SIZE,
1149             tupleSize);
1150
1151    // add the buffer length
1152 setLength(buffer, length + 1);
1153
1154    // subtract from the left length
1155 leftLength -= 1;
1156    setLength(leftBuffer, leftLength);
1157
1158    // copy the entry from the new left tail to the parent
1159 System.arraycopy(leftBuffer,
1160             HEADER_SIZE + (leftLength - 1) * tupleSize + PTR_SIZE,
1161             parentBuffer, parentLeftOffset + PTR_SIZE,
1162             tupleSize - PTR_SIZE);
1163  }
1164
1165  /**
1166   * Returns the index to the left of the current one
1167   */
1168  private void mergeLeft(byte []parentBuffer,
1169             byte []leftBuffer,
1170             byte []buffer,
1171             long blockId)
1172  {
1173    int leftLength = getLength(leftBuffer);
1174    int length = getLength(buffer);
1175
1176    int parentLength = getLength(parentBuffer);
1177
1178    int tupleSize = _tupleSize;
1179    int parentOffset = HEADER_SIZE;
1180    int parentEnd = parentOffset + parentLength * tupleSize;
1181
1182    for (parentOffset += tupleSize;
1183     parentOffset < parentEnd;
1184     parentOffset += tupleSize) {
1185      long pointer = getPointer(parentBuffer, parentOffset);
1186
1187      if (pointer == blockId) {
1188    int leftOffset = HEADER_SIZE + leftLength * tupleSize;
1189
1190    // copy the pointer from the left pointer
1191 setPointer(parentBuffer, parentOffset,
1192           getPointer(parentBuffer, parentOffset - tupleSize));
1193           
1194    // shift the parent
1195 System.arraycopy(parentBuffer, parentOffset,
1196             parentBuffer, parentOffset - tupleSize,
1197             parentEnd - parentOffset);
1198    setLength(parentBuffer, parentLength - 1);
1199
1200    // the new left.next value is the buffer's next value
1201 setPointer(leftBuffer, NEXT_OFFSET,
1202           getPointer(buffer, NEXT_OFFSET));
1203
1204    // append the buffer to the left buffer
1205 // XXX: leaf vs non-leaf?
1206 System.arraycopy(buffer, HEADER_SIZE,
1207             leftBuffer, leftOffset,
1208             length * tupleSize);
1209
1210    setLength(leftBuffer, leftLength + length);
1211
1212    return;
1213      }
1214    }
1215
1216    long pointer = getPointer(parentBuffer, NEXT_OFFSET);
1217
1218    if (pointer != blockId) {
1219      log.warning("BTree remove can't find matching block: " + debugId(blockId));
1220      return;
1221    }
1222    
1223    int leftOffset = HEADER_SIZE + (parentLength - 1) * tupleSize;
1224    
1225    long leftPointer = getPointer(parentBuffer, leftOffset);
1226
1227    setPointer(parentBuffer, NEXT_OFFSET, leftPointer);
1228    setLength(parentBuffer, parentLength - 1);
1229
1230    // XXX: leaf vs non-leaf?
1231
1232    // the new left.next value is the buffer's next value
1233 setPointer(leftBuffer, NEXT_OFFSET,
1234           getPointer(buffer, NEXT_OFFSET));
1235
1236    // append the buffer to the left buffer
1237 System.arraycopy(buffer, HEADER_SIZE,
1238             leftBuffer, HEADER_SIZE + leftLength * tupleSize,
1239             length * tupleSize);
1240
1241    setLength(leftBuffer, leftLength + length);
1242  }
1243
1244  /**
1245   * Returns the index to the right of the current one
1246   */
1247  private long getRightBlockId(Block parent, long blockId)
1248  {
1249    byte []buffer = parent.getBuffer();
1250    
1251    int length = getLength(buffer);
1252
1253    int offset = HEADER_SIZE;
1254    int tupleSize = _tupleSize;
1255    int end = offset + length * tupleSize;
1256
1257    for (; offset < end; offset += tupleSize) {
1258      long pointer = getPointer(buffer, offset);
1259
1260      if (pointer == blockId) {
1261    if (offset + tupleSize < end) {
1262      return getPointer(buffer, offset + tupleSize);
1263    }
1264    else
1265      return getPointer(buffer, NEXT_OFFSET);
1266      }
1267    }
1268
1269    return -1;
1270  }
1271
1272  /**
1273   * Takes the first entry from the right block and moves it to the
1274   * last entry in the current block.
1275   *
1276   * @param parentBuffer the parent block buffer
1277   * @param rightBuffer the right block buffer
1278   * @param buffer the block's buffer
1279   * @param index the index of the block
1280   */
1281  private void moveFromRight(byte []parentBuffer,
1282                 byte []buffer,
1283                 byte []rightBuffer,
1284                 long blockId)
1285  {
1286    int parentLength = getLength(parentBuffer);
1287
1288    int tupleSize = _tupleSize;
1289    int parentOffset = HEADER_SIZE;
1290    int parentEnd = parentOffset + parentLength * tupleSize;
1291
1292    int rightLength = getLength(rightBuffer);
1293
1294    int length = getLength(buffer);
1295
1296    for (;
1297     parentOffset < parentEnd;
1298     parentOffset += tupleSize) {
1299      long pointer = getPointer(parentBuffer, parentOffset);
1300
1301      if (pointer == blockId)
1302    break;
1303    }
1304
1305    if (parentEnd <= parentOffset) {
1306      log.warning("Can't find buffer in deletion borrow right ");
1307      return;
1308    }
1309
1310    // copy the first item in the right to the buffer
1311 System.arraycopy(rightBuffer, HEADER_SIZE,
1312             buffer, HEADER_SIZE + length * tupleSize,
1313             tupleSize);
1314
1315    // shift the data in the right buffer
1316 System.arraycopy(rightBuffer, HEADER_SIZE + tupleSize,
1317             rightBuffer, HEADER_SIZE,
1318             (rightLength - 1) * tupleSize);
1319
1320    // add the buffer length
1321 setLength(buffer, length + 1);
1322
1323    // subtract from the right length
1324 setLength(rightBuffer, rightLength - 1);
1325
1326    // copy the entry from the new buffer tail to the parent
1327 System.arraycopy(buffer,
1328             HEADER_SIZE + length * tupleSize + PTR_SIZE,
1329             parentBuffer, parentOffset + PTR_SIZE,
1330             tupleSize - PTR_SIZE);
1331  }
1332
1333  /**
1334   * Merges the buffer with the right-most one.
1335   */
1336  private void mergeRight(byte []parentBuffer,
1337              byte []buffer,
1338              byte []rightBuffer,
1339              long blockId)
1340  {
1341    int parentLength = getLength(parentBuffer);
1342
1343    int tupleSize = _tupleSize;
1344    int parentOffset = HEADER_SIZE;
1345    int parentEnd = parentOffset + parentLength * tupleSize;
1346
1347    int rightLength = getLength(rightBuffer);
1348
1349    int length = getLength(buffer);
1350
1351    for (;
1352     parentOffset < parentEnd;
1353     parentOffset += tupleSize) {
1354      long pointer = getPointer(parentBuffer, parentOffset);
1355
1356      if (pointer == blockId) {
1357    // add space in the right buffer
1358 System.arraycopy(rightBuffer, HEADER_SIZE,
1359             rightBuffer, HEADER_SIZE + length * tupleSize,
1360             rightLength * tupleSize);
1361    
1362    // add the buffer to the right buffer
1363 System.arraycopy(buffer, HEADER_SIZE,
1364             rightBuffer, HEADER_SIZE,
1365             length * tupleSize);
1366
1367    setLength(rightBuffer, length + rightLength);
1368
1369    // remove the buffer's pointer from the parent
1370 System.arraycopy(parentBuffer, parentOffset + tupleSize,
1371             parentBuffer, parentOffset,
1372             parentEnd - parentOffset - tupleSize);
1373
1374    setLength(parentBuffer, parentLength - 1);
1375
1376    return;
1377      }
1378    }
1379
1380    log.warning("BTree merge right can't find matching index: " + debugId(blockId));
1381  }
1382
1383  /**
1384   * Looks up the next block given the current block and the given key.
1385   */
1386  private long lookupTuple(long blockId,
1387               byte []buffer,
1388                           byte []keyBuffer,
1389                           int keyOffset,
1390                           int keyLength,
1391               boolean isLeaf)
1392    throws IOException
1393  {
1394    int length = getLength(buffer);
1395
1396    int offset = HEADER_SIZE;
1397    int tupleSize = _tupleSize;
1398    int end = offset + length * tupleSize;
1399
1400    while (length > 0) {
1401      int tail = offset + tupleSize * length;
1402      int delta = tupleSize * (length / 2);
1403      int newOffset = offset + delta;
1404
1405      if (newOffset < 0) {
1406    System.out.println("UNDERFLOW: " + debugId(blockId) + " LENGTH:" + length + " STU:" + getLength(buffer) + " DELTA:" + delta);
1407    throw new IllegalStateException ("lookupTuple underflow newOffset:" + newOffset);
1408               
1409      }
1410      else if (newOffset > 65536) {
1411    System.out.println("OVERFLOW: " + debugId(blockId) + " LENGTH:" + length + " STU:" + getLength(buffer) + " DELTA:" + delta);
1412    throw new IllegalStateException ("lookupTuple overflow newOffset:" + newOffset);
1413               
1414      }
1415
1416      int cmp = _keyCompare.compare(keyBuffer, keyOffset,
1417                    buffer, PTR_SIZE + newOffset, keyLength);
1418      
1419      if (cmp == 0)
1420        return getPointer(buffer, newOffset);
1421      else if (cmp > 0) {
1422        offset = newOffset + tupleSize;
1423    length = (tail - offset) / tupleSize;
1424      }
1425      else if (cmp < 0) {
1426    length = length / 2;
1427      }
1428
1429      if (length > 0) {
1430      }
1431      else if (isLeaf)
1432    return 0;
1433      else if (cmp < 0)
1434    return getPointer(buffer, newOffset);
1435      else if (offset == end)
1436    return getPointer(buffer, NEXT_OFFSET);
1437      else
1438    return getPointer(buffer, offset);
1439    }
1440
1441    if (isLeaf)
1442      return 0;
1443    else
1444      return getPointer(buffer, NEXT_OFFSET);
1445  }
1446
1447  /**
1448   * Removes from the next block given the current block and the given key.
1449   */
1450  private long removeLeafEntry(long blockIndex,
1451                               byte []buffer,
1452                               byte []keyBuffer,
1453                               int keyOffset,
1454                               int keyLength)
1455    throws IOException
1456  {
1457    int offset = HEADER_SIZE;
1458    int tupleSize = _tupleSize;
1459    int length = getLength(buffer);
1460
1461    for (int i = 0; i < length; i++) {
1462      int cmp = _keyCompare.compare(keyBuffer, keyOffset,
1463                    buffer, offset + PTR_SIZE,
1464                    keyLength);
1465      
1466      if (0 < cmp) {
1467        offset += tupleSize;
1468        continue;
1469      }
1470      else if (cmp == 0) {
1471    int tupleLength = length * tupleSize;
1472
1473    if (offset + tupleSize < HEADER_SIZE + tupleLength) {
1474      System.arraycopy(buffer, offset + tupleSize,
1475               buffer, offset,
1476               HEADER_SIZE + tupleLength - offset - tupleSize);
1477    }
1478
1479    setLength(buffer, length - 1);
1480        
1481        return i;
1482      }
1483      else {
1484        return 0;
1485      }
1486    }
1487
1488    return 0;
1489  }
1490
1491  /**
1492   * Compares the key to the block data.
1493   */
1494  /*
1495  private int compare(byte []keyBuffer, int keyOffset,
1496                      byte []block, int offset, int length)
1497  {
1498    for (; length > 0; length--) {
1499      byte keyByte = keyBuffer[keyOffset++];
1500      byte blockByte = block[offset++];
1501
1502      if (keyByte < blockByte)
1503        return -1;
1504      else if (blockByte < keyByte)
1505        return 1;
1506    }
1507
1508    return 0;
1509  }
1510  */
1511
1512  private boolean isLeaf(byte []buffer)
1513  {
1514    return (getInt(buffer, FLAGS_OFFSET) & LEAF_FLAG) == 0;
1515  }
1516
1517  private void setLeaf(byte []buffer, boolean isLeaf)
1518  {
1519    if (isLeaf)
1520      setInt(buffer, FLAGS_OFFSET, getInt(buffer, FLAGS_OFFSET) & ~LEAF_FLAG);
1521    else
1522      setInt(buffer, FLAGS_OFFSET, getInt(buffer, FLAGS_OFFSET) | LEAF_FLAG);
1523  }
1524  
1525  /**
1526   * Reads an int
1527   */
1528  private int getInt(byte []buffer, int offset)
1529  {
1530    return (((buffer[offset + 0] & 0xff) << 24) +
1531            ((buffer[offset + 1] & 0xff) << 16) +
1532            ((buffer[offset + 2] & 0xff) << 8) +
1533            ((buffer[offset + 3] & 0xff)));
1534  }
1535
1536  /**
1537   * Reads a pointer.
1538   */
1539  private long getPointer(byte []buffer, int offset)
1540  {
1541    return (((buffer[offset + 0] & 0xffL) << 56) +
1542            ((buffer[offset + 1] & 0xffL) << 48) +
1543            ((buffer[offset + 2] & 0xffL) << 40) +
1544            ((buffer[offset + 3] & 0xffL) << 32) +
1545            ((buffer[offset + 4] & 0xffL) << 24) +
1546            ((buffer[offset + 5] & 0xffL) << 16) +
1547            ((buffer[offset + 6] & 0xffL) << 8) +
1548            ((buffer[offset + 7] & 0xffL)));
1549  }
1550
1551  /**
1552   * Sets an int
1553   */
1554  private void setInt(byte []buffer, int offset, int value)
1555  {
1556    buffer[offset + 0] = (byte) (value >> 24);
1557    buffer[offset + 1] = (byte) (value >> 16);
1558    buffer[offset + 2] = (byte) (value >> 8);
1559    buffer[offset + 3] = (byte) (value);
1560  }
1561
1562  /**
1563   * Sets the length
1564   */
1565  private void setLength(byte []buffer, int value)
1566  {
1567    if (value < 0 || BLOCK_SIZE / _tupleSize < value) {
1568      System.out.println("BAD-LENGTH: " + value);
1569      throw new IllegalArgumentException ("BTree: bad length " + value);
1570    }
1571
1572    setInt(buffer, LENGTH_OFFSET, value);
1573  }
1574
1575  /**
1576   * Sets the length
1577   */
1578  private int getLength(byte []buffer)
1579  {
1580    int value = getInt(buffer, LENGTH_OFFSET);
1581    
1582    if (value < 0 || value > 65536) {
1583      System.out.println("BAD-LENGTH: " + value);
1584      throw new IllegalArgumentException ("BTree: bad length " + value);
1585    }
1586
1587    return value;
1588  }
1589
1590  /**
1591   * Sets a pointer.
1592   */
1593  private void setPointer(byte []buffer, int offset, long value)
1594  {
1595    if (offset <= LENGTH_OFFSET)
1596      System.out.println("BAD_POINTER: " + offset);
1597    
1598    buffer[offset + 0] = (byte) (value >> 56);
1599    buffer[offset + 1] = (byte) (value >> 48);
1600    buffer[offset + 2] = (byte) (value >> 40);
1601    buffer[offset + 3] = (byte) (value >> 32);
1602    buffer[offset + 4] = (byte) (value >> 24);
1603    buffer[offset + 5] = (byte) (value >> 16);
1604    buffer[offset + 6] = (byte) (value >> 8);
1605    buffer[offset + 7] = (byte) (value);
1606  }
1607
1608  /**
1609   * Opens the BTree.
1610   */
1611  private void start()
1612    throws IOException
1613  {
1614    synchronized (this) {
1615      if (_isStarted)
1616    return;
1617
1618      _isStarted = true;
1619    }
1620  }
1621  
1622  /**
1623   * Testing: returns the keys for a block
1624   */
1625  public ArrayList <String > getBlockKeys(long blockIndex)
1626    throws IOException
1627  {
1628    long blockId = _store.addressToBlockId(blockIndex * BLOCK_SIZE);
1629
1630    if (_store.isIndexBlock(blockId))
1631      return null;
1632    
1633    Block block = _store.readBlock(blockId);
1634
1635    block.read();
1636    byte []buffer = block.getBuffer();
1637      
1638    int length = getInt(buffer, LENGTH_OFFSET);
1639    int offset = HEADER_SIZE;
1640    int tupleSize = _tupleSize;
1641
1642    ArrayList <String > keys = new ArrayList <String >();
1643    for (int i = 0; i < length; i++) {
1644      keys.add(_keyCompare.toString(buffer,
1645                    offset + i * tupleSize + PTR_SIZE,
1646                    tupleSize - PTR_SIZE));
1647    }
1648
1649    block.free();
1650    
1651    return keys;
1652  }
1653
1654  public static BTree createTest(Path path, int keySize)
1655    throws IOException , java.sql.SQLException
1656  {
1657    Database db = new Database();
1658    db.setPath(path);
1659    db.init();
1660
1661    Store store = new Store(db, "test", null);
1662    store.create();
1663
1664    Block block = store.allocateIndexBlock();
1665    long blockId = block.getBlockId();
1666    block.free();
1667
1668    return new BTree(store, blockId, keySize, new KeyCompare());
1669  }
1670
1671  public static BTree createStringTest(Path path, int keySize)
1672    throws IOException , java.sql.SQLException
1673  {
1674    Store store = Store.create(path);
1675
1676    Block block = store.allocateIndexBlock();
1677    long blockId = block.getBlockId();
1678    block.free();
1679
1680    return new BTree(store, blockId, keySize, new StringKeyCompare());
1681  }
1682
1683  private String debugId(long blockId)
1684  {
1685    return "" + (blockId % Store.BLOCK_SIZE) + ":" + (blockId / Store.BLOCK_SIZE);
1686  }
1687
1688  public String toString()
1689  {
1690    return "BTree[" + _store + "," + (_rootBlockId / BLOCK_SIZE) + "]";
1691  }
1692}
1693

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags