NAME

Genezzo::Index::bt3 - persistent btree

A btree built of row directory blocks.

SYNOPSIS

 use Genezzo::Index::bt?;

 my $tt = Genezzo::Index::btree->new();

 $tt->insert(1, "hi");
 $tt->insert(7, "there");

DESCRIPTION

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.

FUNCTIONS

functions

insert

delete

EXPORT

none

TODO

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.

AUTHOR

Jeffrey I. Cohen, jcohen@genezzo.com

SEE ALSO

perl(1).

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: jcohen@genezzo.com

For more information, please visit the Genezzo homepage at http://www.genezzo.com