BTree.h

Go to the documentation of this file.

#ifndef INDEX_BTREE_BTREE_H
#define INDEX_BTREE_BTREE_H
 
#include "tdb.h"
 
#include "catalog/IndexDesc.h"
#include "index/BulkLoadIterator.h"
#include "index/Index.h"
#include "index/IndexKey.h"
#include "storage/Record.h"
#include "storage/FileManager.h"
 
namespace taco {
 
typedef RecordId PathItem;
 
struct BTree: public Index {
public:
    class Iterator;
 
    static void Initialize(const IndexDesc *idxdesc);
 
    static std::unique_ptr<BTree> Create(
        std::shared_ptr<const IndexDesc> idxdesc);
 
private:
    BTree(std::shared_ptr<const IndexDesc> idxdesc,
          std::unique_ptr<File> file,
          std::vector<FunctionInfo> lt_funcs,
          std::vector<FunctionInfo> eq_funcs);
 
    std::unique_ptr<File> m_file;
 
    std::vector<FunctionInfo> m_lt_funcs;
 
    std::vector<FunctionInfo> m_eq_funcs;
 
public:
    virtual ~BTree();
 
    void BulkLoad(BulkLoadIterator &iter) override;
 
    bool InsertKey(const IndexKey *key, RecordId recid) override;
 
    bool DeleteKey(const IndexKey *key, RecordId &recid) override;
 
    std::unique_ptr<Index::Iterator> StartScan(const IndexKey *lower,
                                               bool lower_isstrict,
                                               const IndexKey *upper,
                                               bool upper_isstrict) override;
 
    bool IsEmpty();
 
    uint32_t GetTreeHeight();
 
    class Iterator: public Index::Iterator {
    public:
        ~Iterator() {
            EndScan();
        }
 
        bool Next() override;
 
        bool IsAtValidItem() override;
 
        const Record& GetCurrentItem() override;
 
        RecordId GetCurrentRecordId() override;
 
        void EndScan() override;
 
    private:
        Iterator(BTree *btree,
                 ScopedBufferId bufid, SlotId one_before_matching_sid,
                 const IndexKey *key, bool upper_isstrict);
 
        ScopedBufferId m_bufid;
 
        SlotId m_sid;
 
        Record m_rec;
 
        UniqueIndexKey m_upper;
 
        std::vector<Datum> m_upper_data_buffer;
 
        bool m_upper_isstrict;
 
        friend class BTree;
    };
 
private:
    // in index/btree/BTreeUtils.cpp
 
    BufferId CreateNewBTreePage(bool isroot,
                                bool isleaf,
                                PageNumber prev_pid,
                                PageNumber next_pid);
 
    BufferId GetBTreeMetaPage();
 
    void CreateLeafRecord(const IndexKey *key,
                          const RecordId &recid,
                          maxaligned_char_buf &recbuf);
 
    void CreateInternalRecord(const Record &child_recbuf,
                              PageNumber child_pid,
                              bool child_isleaf,
                              maxaligned_char_buf &recbuf);
 
    int BTreeTupleCompare(const IndexKey *key,
                          const RecordId &recid,
                          const char *tuplebuf,
                          bool isleaf) const;
 
    SlotId BinarySearchOnPage(char *buf,
                              const IndexKey *key,
                              const RecordId &recid);
 
    BufferId FindLeafPage(const IndexKey *key,
                          const RecordId &recid,
                          std::vector<PathItem> *p_search_path);
 
    BufferId FindLeafPage(BufferId bufid,
                          const IndexKey *key,
                          const RecordId &recid,
                          std::vector<PathItem> *p_search_path);
 
    SlotId FindInsertionSlotIdOnLeaf(const IndexKey *key,
                                     const RecordId &recid,
                                     BufferId bufid);
 
    void InsertRecordOnPage(BufferId bufid,
                            SlotId insertion_sid,
                            maxaligned_char_buf &&recbuf,
                            std::vector<PathItem> &&search_path);
 
    void CreateNewRoot(BufferId bufid,
                       maxaligned_char_buf &&recbuf);
 
    maxaligned_char_buf SplitPage(BufferId bufid,
                                  SlotId insertion_sid,
                                  maxaligned_char_buf &&recbuf);
 
    SlotId FindDeletionSlotIdOnLeaf(const IndexKey *key,
                                    const RecordId &recid,
                                    BufferId &bufid,
                                    std::vector<PathItem> &search_path);
 
    void DeleteSlotOnPage(BufferId bufid, SlotId sid);
 
    void HandleMinPageUsage(BufferId bufid,
                            std::vector<PathItem> &&search_path);
 
    bool TryMergeOrRebalancePages(BufferId lbufid,
                                  BufferId rbufid,
                                  BufferId pbufid,
                                  SlotId lsid);
 
 
    bool MergePages(BufferId lbufid,
                    BufferId rbufid,
                    BufferId pbufid,
                    SlotId lsid);
 
    bool RebalancePages(BufferId lbufid,
                        BufferId rbufid,
                        BufferId pbufid,
                        SlotId lsid);
 
    // declare the gtest fixture as a friend class
    friend class TestBTree;
    friend class Iterator;
};
 
}   // namespace taco
 
#endif      // INDEX_BTREE_BTREE_H