SQLite для имитации обширной структуры файловой системы?
Мне нужно реализовать своего рода локальную систему постоянного хранения (проще говоря - на диске). Должны быть (виртуальные) папки и файлы.
Каждая папка имеет уникальный идентификатор фиксированного размера, а ожидаемое количество папок довольно велико, может достигать миллионы, и система должна поддерживать это без значительного ухудшения работы. Каждая папка содержит ограниченное количество файлов (~ десятки) произвольного размера. В основном небольшие, но некоторые могут достигать порядка нескольких МБ.
Стоит также добавить, что система будет работать в основном с недавними папками. Вероятность необходимости в старых папках ниже.
Теперь мне нужно спроектировать и реализовать это. Очень наивный подход - реализовать такую систему «буквально», используя файловую систему с плоской иерархией. Но в долгосрочной перспективе это непрактично, поскольку каталог файловой системы на самом деле является объектом, который перезаписывается всякий раз, когда вы добавляете / удаляете что-то в каталоге. Так что создание подкаталога, в котором уже существуют миллионы, - это явно плохая идея.
Лучшим решением было бы расположить все папки в некоторой иерархии (например, в стиле счисления, где первые несколько бит имени каталога определяют первую подпапку, следующие несколько битов определяют следующую подпапку и так далее.
Но есть также возможность хранить все данные в БД, например в SQLite (у меня был хороший опыт работы с этим в прошлом). С правильными индексами это должно быть быстрее, чем просто файловая система (т.е. поиск определенного файла / подпапки). И еще мне нравится возможность модификации в транзакционном режиме (хотя я тоже могу жить без этого).
Пока вариант БД выглядит лучше. Но, похоже, у него тоже есть недостаток. Это связано с тем, что структура реляционной БД - плоский. Означает, что когда мне нужно получить доступ к определенному объекту (файлу) - в основном ищется вся БД. Я не могу выделить какую-то конкретную подпапку. Например, доступ к нескольким файлам в одном каталоге неизбежно приведет к поиску всех файлов этого типа (при условии, что для них есть отдельная таблица) для каждого такого файла, хотя все они «живут» в одном каталоге.
Итак, мой вопрос: звучит ли это как существенный недостаток по сравнению с файловой системой (которая является иерархическая)?
Ответы 2
Нет, не думаю. Я думаю, что базу данных было бы быстрее и проще внедрять и поддерживать.
Ты говоришь:
With proper indexes it should be faster than just file system
а также:
when I need to access a specific object (file) - basically the entire DB is searched. I can't isolate some specific subfolder.
Эти утверждения противоречат друг другу. При правильных индексах все запросы эффективны.
Например:
CREATE TABLE FileSystem (
ID INTEGER PRIMARY KEY,
ParentDir INTEGER REFERENCES FileSystem(ID),
Name TEXT,
Data BLOB -- NULL for directories
);
CREATE INDEX DirNameLookup ON FileSystem(ParentDir, Name);
При чтении файла с именем a/b/c используются эти запросы, каждый из которых может проходить через индекс DirNameLookup:
SELECT ID FROM FileSystem WHERE ParentDir IS NULL AND Name = 'a';
SELECT ID FROM FileSystem WHERE ParentDir = ? AND Name = 'b';
SELECT Data FROM FileSystem WHERE ParentDir = ? AND Name = 'c';
(Вместо использования IS NULL для корневого каталога вы также можете создать строку с известным идентификатором, например, 0 или 1.)
Что вы имеете в виду под словом «найдено»? Что у вас есть его ID?
Это может быть что угодно, применимое к конкретной иерархической структуре: объект открытого каталога, содержащий ссылки файловой системы на содержащиеся в нем файлы, или что-то еще. В любом случае, я хочу сказать, что иерархическая структура любой позволяет выполнять поиск только в определенной области. Тогда как реляционные БД по определению «плоские».
Когда у вас есть идентификатор каталога, вы можете начать поиск в нем. Вы, кажется, неправильно понимаете, как работают индексированные поисковые запросы.
Может, я на самом деле неправильно это понимаю. Индексы дают вам доступ с логарифмической сложностью, а не с O (1) (как прямые указатели). В приведенном вами примере все 3 запроса будут работать в O (log (N)), тогда как N - это общий размер таблицы. Я ошибся?
Да, это журнал (N) (с очень маленьким постоянным коэффициентом, потому что страницы БД большие и кешируются). Чем это отличается от файловой системы или любой другой структуры данных?
В иерархической системе вы платите O (журнал (N)), чтобы найти каталог. Затем в найденном вами каталоге вы платите O (1) за доступ к нужному файлу. Думайте об этом как о карте поиска каталогов, в то время как каждый каталог содержит массив файлов (указателей на), доступ к элементу в массиве - O (1).
И как сохранить ссылку на каталог в файловой системе? (Если бы доступ к файловой системе был таким быстрым, как вы думаете, базы данных сохраняли бы строки как файлы.)
Подумайте об этом как об объектах в памяти с указателями. Говоря концептуально, даже факт, находится ли он в физической оперативной памяти или на диске, не имеет значения.
Я имел в виду, что БД очень эффективна, когда нужно искать «с нуля». Но это может быть менее эффективно (IMHO), чем иерархическая структура, когда вам нужно получить доступ к объекту, когда вы уже «нашли» его родительский элемент.