Использование b деревьев в базе данных
Я должен реализовать базу данных, используя b деревьев для школьного проекта. база данных предназначена для хранения аудиофайлов (песен), и можно выполнить ряд различных запросов, например, запросить все песни данного исполнителя или определенного альбома.
Интуитивно понятная идея - использовать дерево b для каждого поля (песни, альбомы, исполнители,...), проблема в том, что вас могут попросить удалить любого члена любого поля, и в случае, если вы удалите исполнителя, который у вас есть удалить все его альбомы и песни из других деревьев b, помня, что, например, все песни данного исполнителя не обязательно должны быть рядом друг с другом в дереве b, которое соответствует песням.
Мой вопрос: есть ли способ сделать это (удалить песни после того, как было выполнено удаление автора) без необходимости перебирать все элементы других b-деревьев? Я не ищу код просто идеи, потому что все, что я придумал, являются грубыми.
1 ответ
Это мое понимание и может быть не совсем верно.
Обычно в реализации базы данных B-деревья используются для индексов, поэтому, если вы не хотите, чтобы ваш пользователь индексировал каждый столбец, по умолчанию создание B-дерева для каждого поля не требуется. Хотя такое количество индексов приведет к быстрому чтению практически в каждом случае (с индексом по всему, вам не придется выполнять полное сканирование таблицы), это также приведет к очень медленной вставке / обновлению / удалению, поскольку соответствующие данные имеют обновляться в каждом дереве. Как я уверен, вы знаете, что в современных базах данных для вас есть хотя бы один индекс (первичный ключ), поэтому у вас будет хотя бы одно B-дерево с ключом для первичного ключа и указателем на соответствующий узел.
Каждый узел в индексе B-дерева должен иметь указатель / ссылку на полный объект, который он представляет.
Будущие созданные индексы будут включать в себя атрибуты, которые вы укажете в индексе, такие как название песни, исполнитель и т. Д., Однако все равно будут содержать указатель / ссылку на соответствующий узел. Таким образом, когда вы изменяете, скажем, название песни, вы захотите изменить ссылочный узел, на который ссылаются все индексы. Если у вас есть какие-либо индексы, которые имеют измененную ссылку в качестве атрибута, вам придется изменить значения самого индекса.
К сожалению, я верю, что вы правы, полагая, что вам придется грубо форсировать свой путь через другие деревья B при удалении / обновлении, и это один из недостатков использования большого количества индексов (медленное время обновления / удаления). Если вы просто удалите ссылочные узлы, вы, скорее всего, получите указатели на удаленные объекты, которые (в зависимости от вашего языка) дадут вам некоторую форму исключения NullPointerException. Чтобы предотвратить это, их ссылки должны быть удалены со всех деревьев.
Имейте в виду, что полное сканирование ваших индексов все равно будет намного лучше, чем полное сканирование таблиц.