(no subject)

[norian]

Гибридная Графовая База Данных (отвертка с моторчиком для моделирования моделей)

День 7. Индексы : ускорение поиска данных.

Индекс представляет собой отсортированное по возрастанию поле данных плюс оффсеты соответствующих узлов данных в локальных файлах. Чтобы немного повысить скорость выполнения операций, индекс разбит на чанки, которые в лучшем случае помещаются в кэшлайн. Чанки связываются в двунаправленную цепь.

Чтобы искать индекс по значению, надо создать дерево поиска - это следующий этап, поскольку там много функциональности.

На первом этапе индексы поддерживают выбор по логическому условию, но не сортировку (она может быть сделана приложением или потом добавлена как плагин). Также для упрощения поддерживаются индесы только фиксированного размера - для данных переменного размера впоследствии можно будет делать соответствующие хэш функции.

API индексов выглядят как LoadAllDataGE(set& index_offsets, EgByteArrayAbstractType& keyBA) - получить множество файловых оффсетов по ключу и логической операции.


source egIndexes.h

#pragma once
#include <iostream> // debug
#include <fstream>
#include <set>
#include <vector>
// #include <experimental/filesystem> 
#include "egCoreIndexTypes.h"
#include "../service/egByteArray.h"
#include "../service/egFileType.h"
#include "egFingers.h"
// template <typename KeyType> class EgFingers;

class EgIndexesAbstractType { public:
    virtual bool AddNewIndex(EgByteArrayAbstractType& keyBA, uint64_t dataOffset) = 0;
    virtual bool DeleteIndex(EgByteArrayAbstractType& keyBA, uint64_t dataOffset) = 0;
    virtual bool UpdateDataOffset(EgByteArrayAbstractType& keyBA, uint64_t oldDataOffset, uint64_t newDataOffset) = 0;

    virtual bool LoadAllDataEQ(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA) = 0;
    virtual bool LoadAllDataGE(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA) = 0;
    virtual bool LoadAllDataGT(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA) = 0;
    virtual bool LoadAllDataLE(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA) = 0;
    virtual bool LoadAllDataLT(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA) = 0;

    virtual ~EgIndexesAbstractType() {}
};

template <typename KeyType> class EgIndexes : public EgIndexesAbstractType { public: // indexes chain part of indexes-fingers complex
    const uint64_t            indexHeaderSize       = sizeof(uint64_t);
    const egMaxStreamSizeType oneIndexSize          = sizeof(KeyType) + sizeof(uint64_t); // key and data offset
    const egMaxStreamSizeType fwdPtrPosition        = egIndexesSpace::egChunkCapacity * oneIndexSize;
    const egMaxStreamSizeType backPtrPosition       = fwdPtrPosition   + sizeof(uint64_t);
    const egMaxStreamSizeType chunkCountPosition    = backPtrPosition  + sizeof(uint64_t);
    const egMaxStreamSizeType fingersChunkOffsetPosition  = chunkCountPosition + sizeof(keysCountType);
    const egMaxStreamSizeType indexChunkSize        =  fingersChunkOffsetPosition + sizeof(uint64_t);

    bool fingersChainFlag {true};
    KeyType  theKey;                // index key to process
    uint64_t theDataOffset;         // offsets in data nodes file
    uint64_t theNewDataOffset;
    uint64_t theOldDataOffset;
    keysCountType theChunkCount;    // indexes count in the chunk for chain opers
    uint64_t theIndexesChunkOffset; // file position for chain connect
    int      theIndexPosition;      // position in the chunk
    uint64_t prevOffsetPtr;         // chunks chain operations
    uint64_t nextOffsetPtr;
    uint64_t currentIndexQuantity;  // position savepoint for Load*DataNext functions
    uint64_t currentChunkOffset;    // chunk savepoint for Load*DataNext functions
    keysCountType  transactionPosInChunk; // chunk position savepoint for Load*DataNext functions
    uint64_t reallyLoaded  {0};     // first/next opers support
    uint64_t transactionID {0};     // FIXME TODO first/next opers support

    EgFingers<KeyType>*     fingersTree {nullptr};  // fingers tree object ptr
    EgDataStream*           localStream {nullptr};  // chunk buffer operations
    EgIndexStruct<KeyType>  indexData;              // index data wrapper for flexibility
    EgFileType              indexFileStream;        // file operations
    std::string             indexFileName;
    
    EgIndexes(const std::string a_indexName);
    virtual ~EgIndexes() { delete localStream; }
        // top API
    bool AddNewIndex(EgByteArrayAbstractType& keyBA, uint64_t dataOffset) override;
    bool DeleteIndex(EgByteArrayAbstractType& keyBA, uint64_t dataOffset) override ;
    bool UpdateDataOffset(EgByteArrayAbstractType& keyBA, uint64_t oldDataOffset, uint64_t newDataOffset) override;
        // load data top API
    bool LoadAllDataFirst(std::set<uint64_t>& index_offsets, uint64_t& maxQuantity);
    bool LoadDataNextUp (std::set<uint64_t>& index_offsets, uint64_t& maxQuantity);

    bool LoadAllDataEQ(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA);
    bool LoadAllDataGE(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA);
    bool LoadAllDataGT(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA);
    bool LoadAllDataLE(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA);
    bool LoadAllDataLT(std::set<uint64_t>& index_offsets, EgByteArrayAbstractType& keyBA);
};