BTreeBuilder.h

Go to the documentation of this file.

/*
// $Id: //open/dev/fennel/btree/BTreeBuilder.h#11 $
// Fennel is a library of data storage and processing components.
// Copyright (C) 2005-2009 The Eigenbase Project
// Copyright (C) 2005-2009 SQLstream, Inc.
// Copyright (C) 2005-2009 LucidEra, Inc.
// Portions Copyright (C) 1999-2009 John V. Sichi
//
// 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 (at your option)
// any later version approved by The Eigenbase Project.
//
// 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef Fennel_BTreeBuilder_Included
#define Fennel_BTreeBuilder_Included

#include "fennel/btree/BTreeAccessBase.h"

#include <vector>

FENNEL_BEGIN_NAMESPACE

class BTreeBuildLevel;
typedef boost::shared_ptr<BTreeBuildLevel> SharedBTreeBuildLevel;

// TODO:  doc internals

class FENNEL_BTREE_EXPORT BTreeBuilder
    : public BTreeAccessBase
{
    // TODO:  something better
    friend class BTreeBuildLevel;
    friend class FixedBuildLevel;
    friend class VariableBuildLevel;
    friend class DynamicBuildLevel;

    std::vector<SharedBTreeBuildLevel> levels;

    SharedSegment pTempSegment;

// ----------------------------------------------------------------------
// internal helper methods
// ----------------------------------------------------------------------

    static uint calculateChildEntriesPerNode(
        RecordNum parentLevelTotalEntries,
        RecordNum childLevelTotalEntries,
        RecordNum parentLevelProcessedEntries);

    static uint calculateNodesOnLevel(
        uint nChildEntries,uint nEntriesPerChildNode);

    uint getRootHeight()
    {
        return levels.size() - 1;
    }

    void buildBalanced(
        ByteInputStream &sortedStream,
        uint iInputLevel,
        RecordNum nEntriesTotal,
        double fillFactor);

    void buildTwoPass(
        ByteInputStream &sortedStream,
        RecordNum nEntries,
        double fillFactor);

    void buildUnbalanced(
        ByteInputStream &sortedStream,
        RecordNum nEntries,
        double fillFactor);

    void processInput(
        ByteInputStream &sortedStream);

    inline BTreeBuildLevel &getLevel(uint i);

    void growTree();

    void swapRoot();

    void truncateChildren(BTreeNode const &node);
    void truncateExternal(TupleProjection const &leafPageIdProj);

public:
    explicit BTreeBuilder(
        BTreeDescriptor const &descriptor,
        SharedSegment pTempSegment = SharedSegment());
    virtual ~BTreeBuilder();

    void build(
        ByteInputStream &sortedStream,
        RecordNum nEntries,
        double fillFactor = 1.0);

    void createEmptyRoot();

    void truncate(
        bool rootless,
        TupleProjection const *pLeafPageIdProj = NULL);
};

inline BTreeBuildLevel &BTreeBuilder::getLevel(uint i)
{
    return *(levels[i]);
}

FENNEL_END_NAMESPACE

#endif

// End BTreeBuilder.h

---