Genezzo::Index::bt3 - persistent btree
A btree built of row directory blocks.
use Genezzo::Index::bt?; my $tt = Genezzo::Index::btree->new(); $tt->insert(1, "hi"); $tt->insert(7, "there");
This btree algorithm is a bottom-up implementation based upon ideas from Chapter 16 of "Algorithms in C++ (third edition)", by Robert Sedgewick, 1998 and Chapter 15, "Access Paths", of "Transaction Processing: Concepts and Techniques" by Jim Gray and Andreas Reuter, 1993. The pedagogical examples use a fixed number of entries per node, or fixed-size keys in each block, but this implementation has significant extensions to support variable numbers of variably-sized keys in fixed-size disk blocks, with the associated error handling, plus support for reverse scans.
- new: maybe a way to get blocksize from rstab/rsfile and pass to bt2, versus passing it to each layer separately
- getMainMeta from first block of tied hash, but no guarantee that space management is nice enough to return blocks in allocation order. Should store block address of leftmost leaf in index table.
- spacecheck: space cache should simply be free extents allocated to the index. Need to extend smfile to have multiple free extents in spacelist, vs just used extents. Note still an issue for simultaneous inserts -- need lots of space for pathological case where each parallel insert splits a separate subtree. That's why transactions were invented.
Jeffrey I. Cohen, email@example.com
Copyright (c) 2003, 2004 Jeffrey I Cohen. All rights reserved.
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Address bug reports and comments to: firstname.lastname@example.org
For more information, please visit the Genezzo homepage at http://www.genezzo.com