Проектирование БД: наследование

Ну понятно, но это же надо поддерживать этот регион в актуальном состоянии, а потом произойдёт слияние регионов, разделение регионов и это всё просто не решается средствами sql, надо что-то городить вообще сбоку.

Так SQL для данных, а не для алгоритмов. Да, разделение регионов для данной структуры будет дорогой операцией.

В смысле? У нас каждая папка ровно в одной папке.

Ну то есть найти всех потомков 5 - «%/5/%». 1 - «%/1/%», путь будет «/1/5/20/».

Это сколько же записей в папке должно быть, чтобы оно полдня по ним UPDATE делало? 4 миллиарда?

Почему бы и нет. Или запросов очень много. Да и всякие операции типа перемещения тоже так себе. Был путь /a/b/c/d/e стал /e/f/z/x/c/d/e/, если были бы нормальные ссылки менялась бы только ссылка на c: из b удалили, в x добавили. А так - ползай по всей таблице. И я не усложняю еще всякими хардлинками.

Да, разделение регионов для данной структуры будет дорогой операцией.

Если есть тупо механизм обхода ссылок, то это не слишком дорого и сложно, при условии, что нет цикличных связей. Проблема в том, что в рбд нет ссылок, тут просто числа, которые могут лежать в индексе, из которого получается ссылка. Для таких задач нужны какие-то механизмы, которые будут описывать структуру индекса, т.е. btree - должен быть не какой-то внутренней фичей, а просто частным случаем реализации индекса. Если бы это можно было делать, то можно было бы и регионы в графе выбирать не особо напрягаясь.

Ну то есть найти всех потомков 5 - «%/5/%». 1 - «%/1/%», путь будет «/1/5/20/».

Если 5 — прямой потомок 1, а 1 — корневая папка, то путь будет «1/5/%» и «1/%» и никаких произвольных символов в начале пути быть не может.

Был путь /a/b/c/d/e стал /e/f/z/x/c/d/e/, если были бы нормальные ссылки менялась бы только ссылка на c: из b удалили, в x добавили. А так - ползай по всей таблице.

Ну да, а так будет всюду замена префикса «/a/b/c/» на «/e/f/z/x/c/». Но, как правило, такие операции редки. Кстати, ACL на файловую систему также в каждом файле хранятся. Где-то в корне права поменяешь, будет менять во всех файлах. Так как операция достаточно редкая (а чтение — частая). То есть весь вопрос, под что оптимизируем.

Проблема в том, что в рбд нет ссылок, тут просто числа, которые могут лежать в индексе, из которого получается ссылка.

Ссылка — это всегда всего лишь число. А уж получается по этому числу объект из памяти или строка из таблицы БД — детали реализации.

Для таких задач нужны какие-то механизмы, которые будут описывать структуру индекса, т.е. btree - должен быть не какой-то внутренней фичей, а просто частным случаем реализации индекса.

И какой же индекс помог бы при делении графа на регионы? Вот как бы по-твоему должно было бы быть устроено идеальное хранилище данных?

Проблема в том, что в рбд нет ссылок

Ну не знаю, я на ваши препирательства смотрю как возню с совой и глобусом... Можешь представить свои данные в табличном виде (1 поле - одна неделимая сущность) - бери РСУБД, не можешь - бери что угодно другое...

Так и с деревом: можешь связь обеспечивать через f.key, можешь на уровень выделять отдельную таблицу, можешь при небольшой глубине дерева распихивать его по полям одной записи, если всё не подходит - бери другой инструмент.

Субд плохо справляются, например, с иерархическим деревом. Тупо хранить parent_id - всё ок, но делать выборку всех потомков - уже начинаются всякие костыли, переподвыборки, встроенные язычки и сделать это проще на любом мейнстримном яп.

Nested Sets?

никаких произвольных символов в начале пути быть не может.

Они нужны, без них начало и конец пути - спецкейс.

Ссылка — это всегда всего лишь число. А уж получается по этому числу объект из памяти или строка из таблицы БД — детали реализации.

Так в рбд этому числу ничего не соотвествует физически. Чтобы что-то выяснить надо переться каждый раз в индекс.

И какой же индекс помог бы при делении графа на регионы?

Зачем были бы нужны регионы, если бы был быстрый индекс?

Вот как бы по-твоему должно было бы быть устроено идеальное хранилище данных?

Для рбд нужны, например, пользовательские реализации индекса на каком-нибудь язычке, который бы компилировался. В оракле что-то есть на жабке, но говорят, что там совсем уныло.

бери РСУБД, не можешь - бери что угодно другое...

Ну и что, ради одной таблицы брать графовую бд и колотить вокруг забор из костылей? Тут из-за трёхзвенки у всех истерика.

Так и с деревом: можешь связь обеспечивать через f.key, можешь на уровень выделять отдельную таблицу, можешь при небольшой глубине дерева распихивать его по полям одной записи, если всё не подходит - бери другой инструмент.

Ну так я и говорю, что рбд не поддерживают нормально ссылки, а мне не верят. Любая задача, которая легко решается ссылками тут превращается в строковые поля с путями и подобный изврат.

Это не изврат, это хранение табличных данных. Ссылки есть - f.key. Не получается «красиво» разложить свои данные в табличный вид? Но это не проблема РСУБД, это проблема «разложения» некоторых данных в табличный вид. Это обычная задача при работе с «реляционками», и как правило она не имеет единственного верного решения, и многое зависит от различных факторов.

Ну нельзя от шоссейного тягача ждать езды по бездорожью, а от гусеничного транспортёра - экономной и быстрой доставки груза по шоссе.

Ну и что, ради одной таблицы брать графовую бд и колотить вокруг забор из костылей?

Ради одной таблицы, описывающей древовидную структуру организации, с глубиной не более 10-ка и количеством нод не дотягивающем до тысячи, не стоит даже разводить срачь «РСУБД плохо натягивается на граф».

Они нужны, без них начало и конец пути - спецкейс.

В смысле спецкейс? Для любого элемента p все элементы под ним всегда соответствуют условию LIKE p.full_path + '/%'.

Так в рбд этому числу ничего не соотвествует физически. Чтобы что-то выяснить надо переться каждый раз в индекс.

Зависит от реализации СУБД. Никто не мешает транслировать мелкие таблицы с числовым ключом в массивы в памяти. В Oraсle есть rowid из которого арифметически вычисляется позиция в файле БД.

пользовательские реализации индекса на каком-нибудь язычке, который бы компилировался

В смысле, чтобы суррогатные колонки для индексации не создавать? Или тебя хранение в виде дерева не устраивает?

LIKE p.full_path + '/%'.

А из середины пути?

В смысле, чтобы суррогатные колонки для индексации не создавать? Или тебя хранение в виде дерева не устраивает?

Когда-то устраивает дерево, когда-то дерево не устраивает. Нужен бы какой-то выбор, но есть только btree и велосипеды вокруг него.

Никто не мешает транслировать мелкие таблицы с числовым ключом в массивы в памяти.

Ну да, я так и делаю. Выбираю всё, что можно и ковыряюсь с этим на нормальном яп.

В Oraсle есть rowid из которого арифметически вычисляется позиция в файле БД.

А как сделать из этих rowid, например, связанный список, чтобы выборка n значений не превратилась в n запросов?

Ради одной таблицы, описывающей древовидную структуру организации

У меня не древовидная структура организации и связей около миллиона (10М в перспективе). Ну пути не очень длинные, но тут всё не точно и не ясно что будет дальше. В любом случае тяну всё из базы, потому что выборки делать тупо не удобно.

А из середины пути?

Так p не обязательно в начале пути. Работает из любой точки иерархии. Или что значит «из середины пути»?

Ну да, я так и делаю. Выбираю всё, что можно и ковыряюсь с этим на нормальном яп.

Я имел в виду, что нормальный оптимизатор СУБД должен сам так делать.

Если «Выбираю всё, что можно и ковыряюсь с этим на нормальном яп.», то лучшая база — таблички dbf. Сверхбыстрая работа при линейном чтении, возможность явного указания, использовать или нет индекс (и вообще возможность велосипедить индекс любой структуры), возможность хранить ссылки на строки таблицы (при mmap они даже будут как обычные ссылки на объект в памяти).

А как сделать из этих rowid, например, связанный список, чтобы выборка n значений не превратилась в n запросов?

А как то же самое из обычных ссылок сделать, чтобы выборка n значений не превратилась в n переходов по ссылке? Выборка по rowid эквивалент перехода по ссылке.

Ну чтобы по одному ид найти всё, что ниже, а на тащить весь путь. Хотя это не нужно.

Ну чтобы по одному ид найти всё, что ниже, а на тащить весь путь.

SELECT r.* from tree as r JOIN
SELECT full_path FROM tree as p 
ON r.full_path LIKE p.full_path+"/%"
AND p.id = @id

два индексированных подзапроса.

А как то же самое из обычных ссылок сделать, чтобы выборка n значений не превратилась в n переходов по ссылке? Выборка по rowid эквивалент перехода по ссылке.

Ну, смотри. Мне надо выбрать связанный список. Я говорю субд, хочу список с такого-то id. У неё этот список в индексе в виде btree, где ноды дополнительно связаны в список. Он находит мне в дереве id и потом пробегает по ссылкам до конца, собирает всё это в список offsetoв и лезет с этим к диску. В идеале как-то так. С другими структурами будет всё по-другому.

Он находит мне в дереве id и потом пробегает по ссылкам до конца, собирает всё это в список offsetoв и лезет с этим к диску.

Чтобы пробежать по ссылкам до конца их сначала надо с диска прочитать. Или их должно быть достаточно мало, чтобы они помещались в память.

Вроде как Oracle в хранимых процедурах при работе через первичный ключ такое позволяет. То есть SELECT p.next from list where p.id = @id транслируется в что-то типа @id.next. И тогда хранимкой действительно можно пройти по списку и вернуть массив идентификаторов, не обращаясь к диску (будет один доступ через хэш + n доступов по ссылке, всё в памяти).

Чтобы пробежать по ссылкам до конца их сначала надо с диска прочитать. Или их должно быть достаточно мало, чтобы они помещались в память.

Ну если это индекс, то они не большие и висят в памяти целиком.

И тогда хранимкой действительно можно пройти по списку и вернуть массив идентификаторов, не обращаясь к диску

Ну да, есть какие-то отдельные решения, но всё это как-то для спецкейсов чисто и надо думать о том, схавает твоя субд такое или нет. Было бы общее какое-то решение, что пишешь индекс на какой-нибудь такой же хранимке он компилируется и работаешь по нему из sql задаваемыми функциями.

Ну если это индекс, то они не большие и висят в памяти целиком.

Не большие? У меня в 1С в бухгалтерское базе .cdx файлы по несколько гигабайтов были. И данные поля next — это уже не индекс. Технически это отдельная таблица с двумя полями.

Было бы общее какое-то решение, что пишешь индекс на какой-нибудь такой же хранимке он компилируется и работаешь по нему из sql задаваемыми функциями.

DBF. И xHarbour в качестве языка доступа.

На хорошей таблице такая команда будет выполняться полдня

ну так ты голову хоть иногда включай и не коммить всё одним заходом

ну так ты голову хоть иногда включай и не коммить всё одним заходом

А в n заходов оно будет делать update быстрее? Интересный вопрос, кстати.

У меня в 1С в бухгалтерское базе .cdx файлы по несколько гигабайтов были

По сравнению с таблицей - это всё равно не много. Да и когда памяти 256гб на сервере - не редкость даже для нашего аула.

И данные поля next — это уже не индекс.

В зависимости от того, как он организован. Как это делают обычно в рбд - да, не индекс и по нему не побегаешь. О чем и речь.

DBF

Всё плохо с множественным доступом.

Всё плохо с множественным доступом.

Чем плохо? Многопользовательский доступ работает вполне успешно. Транзакции, также как и индексы, полностью контролируется программой. Просто низкоуровневой работы много, но ты сам пишешь, что нужен контроль и возможности.

А в n заходов оно будет делать update быстрее?

как минимум таблица не будет залочена на время всей операции. прям классика погромистов, даны ведь вам bulk collect, forall, fetch, limit и ко, но вы продолжаете удивлять локами и ронять базы.