Я много искал, но не нашел в этом ничего объективного или окончательного.
Я хотел бы узнать, как построить индекс, структурированный как B-дерево. Есть два файла:
main.bin (файл, в котором хранятся все мои регистры фиксированного размера, идентифицированные ключом, файл, который я индексирую)
index.bin (B-Дерево, индекс, сохраненный во вторичной памяти).
В файле индекса каждый ключ k несет RRN , то есть смещение байта, гдерегистр ключа k - это запись в файле, который я индексирую (основной файл).
Моя идея заключается в разработке на C. Я подумал о следующих структурах для узлов B-Дерево:
//Macro Definitions:
#define ORDER 5 /* Order of a B-Tree defined by Donald Knuth:
Max Number of children that every node can have ==
Max Number of keys that every node can have plus one. */
//Type Data Definitions:
typedef struct{
char key; //Primary key.
int RRN; //The pointer to the RNN of the register of the key of the main file.
}keyReference;
typedef struct{
int keyCount; //Number of keys in this page.
keyReference vetor[ORDER - 1]; //The keys with its references (RRN's).
int child[ORDER]; //Pointers to the RRN's of descendants.
}bTreePage;
Но возникает вопрос: как создать и сохранить (вторичную память) индекс, структурированный как B-дерево? Какова организация дерева в файле на диске?
Любая помощь? :) Спасибо за чтение.