Реализация BTree. Нужно ли сначала знать порядок дерева?
Итак, у меня есть проект для моего класса структур данных, и я должен реализовать очень простую информационную базу данных. Записи должны храниться в файле, а когда программа открыта — их нужно прочитать из файла и поместить в BTree. Моя проблема в том, что мы до сих пор не говорили о BTrees, и лекция в учебнике не слишком ясна (в ней нет кода, только объяснения и несколько примеров).
Мой вопрос: могу ли я создать BTree, не зная сначала его порядок? Или я должен просто установить очень большое число для заказа, чтобы быть уверенным, что он сможет вместить много записей? Какие-либо предложения?
Решение
Вы, конечно, можете — BTrees предназначены для сортировки их ввода. Все, что нужно, — это способность сравнивать любые два ваших объекта и уметь определять, какой из них «больше» или должен идти позже. BTree динамически растут, когда вы добавляете к ним больше предметов, увеличивая их уровни. Я надеюсь, что ваш профессор хорошо знаком с BTrees, поскольку они представляют собой увлекательную структуру :-).
Если вы ожидаете, что BTree будет реализован как часть вашего назначения, вам нужно будет обратиться к TA и попросить их объяснить это подробно — общая идея заключается в том, что каждый узел является либо тем, у которого есть значения, отсортированный или тот, который указывает на другие узлы, на основе диапазонов значений. Каждый раз, когда вы добавляете узел в это дерево, вы идете туда, где должен быть узел, и добавляете узел, если это возможно. Если нет, вы реорганизуете дерево до тех пор, пока это возможно, а затем добавляете узел.
Дьявол кроется в деталях, и детали в этом случае потребуют некоторого времени и хорошего объяснения, чтобы полностью впасть в уныние. Причина, по которой люди терпят головную боль по всем причинам сложности, заключается в том, что BTrees не нужно заранее знать, насколько большими они будут в конечном итоге, какой диапазон будут охватывать элементы или что-то еще. В качестве бонуса, они очень хорошо подходят для использования на диске, где вы даже не можете хранить все элементы в памяти.
Другие решения
Если вы внедряете свой собственный BTree, то вы должны убедиться, что он может поддерживать разные заказы, в частности, потому что порядок, который вы хотите использовать, будет зависеть от среды. Назначение BTree состоит в том, чтобы минимизировать время, необходимое для случайного доступа, поэтому BTree в памяти (если вы будете использовать его таким образом) будет хотеть, чтобы один узел помещался в строку кэша, и если вы собираетесь чтобы хранить BTree на диске (что вы будете делать в этом случае), вы хотите, чтобы ваши узлы помещались в сектор диска.