View on
MetaCPAN
search.cpan.org is shutting down
For details read Perl NOC. After June 25th this page will redirect to MetaCPAN.org
Jeffrey Cohen > Genezzo > Genezzo::Index::bt3

Download:
Genezzo-0.72.tar.gz

Dependencies

Annotate this POD

CPAN RT

Open  1
View/Report Bugs
Source  

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

syntax highlighting: