Деревья в БД
Иерархические структуры данных не просто хранить в реляционных Базах Данных (БД).
Плоская модель таблиц не позволяет гибко работать с вложенными сущностями.
Изыскания на этот счёт давно идут. Ищется способ совместить реляционные свойства и NoSQL, например, сохранив декларативность запросов. Ищется способ хранить гетерогенные структуры в таблицах БД.
Я выложу тут обзор возможных решений известных мне.
Полезное
Начну с полезной ссылки … вдруг вы сами хотите разобраться глубоко в этом вопросе
http://911datasets.org/index.php/Help:Tree_Structures
про хранение деревьев в реляционных БД.
Тут есть почти все, что надо знать для начала работы с этой проблемой.
собаковды рекомендуют; главные идеи
Чаще всего такую тему начинают с одной презентации, известной «всем».
Презентация по моделям данных для хранения «деревяшек» от чувака из Percona — непререкаемых лидеров в вопросах sql движков… и что же они (он) рекомендуют?:
чтобы уловить суть смотрите сразу на слайд № 69. — там сравнение описанных ранее способов.
Есть четыре главных способа:
- Adjacency List
- Path Enumeration
- Nested Sets
- Closure Table
есть и другие… наиболее полный обзор тут http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database
по сложности операций с данными они имеют разный вес и приходится платить за это разную цену… в этом собственно и дилема — все же лучше прочитать презентацию подробно (для тех кто сразу перелистнул на слайд 69).
о задаче. задача такова: надо быстро выполнять операции:
- вставка значений в дерево, их перенос в другую ветку
- получение непосредственных «чилдов»
- получение родителя и дедушек
- получение всех вложенных листьев (возможно, до некоторой глубины)
- удаление веток в дереве
чтобы делать это быстро структура данных должна способствовать, а ведь мы же в БД….реляционной… вот и суть проблемы. пошли дальше.
ClosureTable выглядит наиболее серьёзно — делает все необходимые операции быстро, но ! ClosureTable требует чтобы был специальный индекс, объём данных в котором ~N*N, т.е. не линеен (сильно растёт с ростом глубины дерева). Это плата за скорость — иногда ограничивает до полной неприемлемости всего метода.
ClosureTable (CT)
метод с примером описан тут
http://technobytz.com/closure_table_store_hierarchical_data.html
Итак, метод кажется привлекательным, но не все пользуются, например тут http://stackoverflow.com/questions/7497812/hierarchical-data-in-a-database-recursive-query-vs-closure-tables-vs-graph-da читают его избыточным в устройстве и рекомендуют использовать для решения задачи рекурсивные запросы.
вот еще пример запросов к CT
http://stackoverflow.com/questions/23030755/depth-in-mysql-and-closure-table-trees/23134613#23134613
опять рекомендуют иерархические запросы
http://stackoverflow.com/questions/6533742/print-a-complete-transitive-closure-tree/6534336#6534336
рекурсивные запросы — крутая фича БД которая отсутствует в большинстве движков. Она дорого стоит при обработке, хотя меньше чем хранимая процедура с циклами. На ExecutionPlan рекурсивного запроса сложно влиять в процессе оптимизации запроса.
Например, в mysql жалкие попытки работы с деревьями выглядят убого http://stackoverflow.com/questions/1316126/how-can-i-find-all-siblings-to-my-node-and-its-anchestors-in-a-hierarchical-cate
по Mysql есть хорошая книжка «Managing Hierarchical Data in MySQL»
http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
и ClosureTable там нет — «геморно».
ORM
ORM = Object Relation Mapper (ing)
Это подмножество решений позволяет отображать наш объектный мир ПО на плоскую реляционную БД. и работать с разными БД в качестве бекендов.
Хранение иерархий может решать на уровне ORM. Так то же имеется ?
PHP
в PHP есть такая шняга штука Doctrine 2. Вот пример кода для ClosureTable
и как бы я не ругал PHP — для него есть не плохие либы…
хорошо, что не php единым — Python
прекрасный язык, прекрасные либы, все самое вкусное… не без магии, но красиво: Peewee http://docs.peewee-orm.com/en/latest/ — мой любимый.
для него есть коллекция расширений, например шикарное расширения для sqlite бекенда:
Querying Tree Structures in SQLite using Python and the Transitive Closure Extension http://charlesleifer.com/blog/querying-tree-structures-in-sqlite-using-python-and-the-transitive-closure-extension/
Парни, именно так надо делать расширения, удобно и понятно. таких расширений надо больше, выше и сильнее 🙂
TODO пример кода SQL и для peewee
Решения на уровне самой БД
сначала напишу, что сам пользовал.
Transact SQL(MS)
hierarchyid — системный тип базы данных в Transact-SQL
статья http://habrahabr.ru/post/27774/
коменты к статье на хабре — не хуже самой статьи отражают проблематику.
PostgresSQL
ltree
в PG из коробки есть хорошая основа для метода «Path Enumeration» за счёт работы с GIST индексами и полем ltree.
дока : http://www.postgresql.org/docs/9.1/static/ltree.html
статья на хабре по русски: http://habrahabr.ru/post/130371/
метод хорош (не плох), но без либы специальной юзать это не удобно — нужна либа. я не нашёл, круто было бы если бы pqlib сам бы умел… ээх, мечты.
Рекурсивные запросы PG
в PG есть рекурсивные запросы, а значит можно хоть на ушах ходить обходить в глубину, ширину свои структуры с простыми полями parent… это расхолаживает и радует.
выглядит это примерно так http://stackoverflow.com/questions/28688264/how-to-traverse-a-hierarchical-tree-structure-structure-backwards-using-recursiv/28709934#28709934
Вы скажете: «хорошо, PG умеет это. а я хочу работать в tornado с БД асинхронно, можно это удобно сделать ?». ответ: ДА.
momoko PG tornado extention — пользуйтесь на здоровье. https://github.com/FSX/momoko/blob/master/docs/tutorial.rst
давненько для себя я сделал один вывод: если ты выбрал PG — у тебя все будет. мегаплатформа, он будет расти в твоих глазах вместе с тобой (только не лезь в код, я пробовал… расстроишься).
TODO привести пример рекурсивного запроса по иерархии в PG
Потом напишу что сам НЕ пользовал, но видел глазами:
MySql
Посмотрите тут примеры
http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/
Oracle
CONNECT BY
http://www.ypl.com/oracle/sql/hierarchical_queries/html_deep/index.html
Послесловие
Напоследок рекомендую посмотреть этот pdf для саморазвития. https://vadimtropashko.files.wordpress.com/2011/07/ch5.pdf
Как вам матричная форма адресации ? Nested Intervals ?
Исследования в этой области еще имеют потенциал, возможно именно Вы придумаете ещё один самый лучший способ быстро работать с деревом в БД, придумаете свой способ, на базе …. ну не знаю, например на базе математического аппарата теории суперструн 🙂
PS
хорошая либа для питона
https://libtree.readthedocs.org/en/latest/index.html
код с расширением для sqlite
В мои планы входит «сравнить производительность метода recursive select для PG и метода AList из библиотеки tree для Python и метода на ltree поставки PG», но не хватет времени. Тема дляДиплома студенту ?
Библиотека доступа к иерархическим страктурам, хранимым в реляционных БД.
————
а вот коммент чувака по поводу производительности PG libtree — https://www.reddit.com/r/Python/comments/3qk51f/showcase_libtree_simple_fast_and_powerful_tree/?
Он утрверждает, по реальным тестам , что масштабируемость до миллиона узлов характерна для SELECT, вставка естественно замедляется при росте дерева «в глубину».
Роман
09.12.2015 в 18:57А чем графовые БД не устраивают? Например, TitanDB. Позволяет эффективно хранить структуры произвольной связности. Лично я использую язык запросов Gremlin (под эгидой TinkerPop), но есть ещё SPARQL, который очень похож на SQL. В последней версии Gremlin тоже поддерживает нечто похожее на sparql. 6e+6 вершин и >18e+6 рёбер на одной машине с 16 гб памяти вполне держит. К вершинам можно присандаливать свойства (которые могут иметь сложную структуру). Есть ORM. Правда, лично для меня он не подошел и пришлось сделать порт Gremlin для Python (https://github.com/windj007/python-gremlin-rest).
Михаил Павлов
15.12.2015 в 11:55Ром, привет.
1) TitanDB в первый раз вижу, спасибо. я как-то графовые бд вот не затронл пока. с него начну.
2) если не в реляционной бд хранить, то уже много решений, тут согласен. Можно привести много примеров. а статья про то, как оставаясь в рамках классической реляционной БД, работать эффективно хотябы с дервьями.
статья обзорно описывает со ссылками известные способы предствления дерева в реляционном виде и показывает, как можно средствами rdbms (возможно уникальными средствами для конкретной БД) решать задачи выбора узлов.
3) мы как-то написали свою хранилку древьев с планаризатором (инкрементальная планаризация по мере изменения дерева делалась, без полного обхода, сохраняли дерево планаризованным)
об этом я написал тут
а тут я попробовал его сконвертировать с питона на JS и для этого даже транслятор пришлось доработать
НО! это оказалось фиговой идеей по сравнению с обычной БД.
в продакшене кроме этой штуки нужно:
* бекапы делать консистентные
* масштабировать как-то так, чтобы не учить никого а дать тупо туториал
* у нас в системе хочется иметь связанные данные хранимые в обычной БД бе выкрутасов
* есть представления, оказывается (внезапно), для которых планаризация это не главное
* чтобы делать рапределенную версию , то это иная стоимостьрешения, а мы уже так делать её не хотим.
получается, что в нашем случае проще всё таки посмотреть в сторону типовой RDBMS.
а графы для нас пока экзотика. по графам у меня вопрос: «а на сколько эффективно вних вообще строятся индексы для сложных запросов типа join join join ? «. я плохо их знаю и хочу занть, есть ли инструменты которые помогают делать аналитику по таким наборам данных ? расскажи плиз, что знаешь.
Роман
17.12.2015 в 12:19Прошу прощения, не туда комментарий добавился. см. https://srv.nppsatek.ru/blogs/?p=383#comment-163
Роман
16.12.2015 в 17:34Судя по тому, что ты написал, складывается впечатление, что наоборот, РСУБД вам вообще не подходят. РСУБД проще всех остальных только тем, что там есть ОРМ и привычные термины/подход к проектированию. В свою очередь, ОРМ даёт серьёзный выигрыш только в случае более-менее сложных моделей, когда больше 20 таблиц (зависит от квалификации разработчиков). Подход к проектированию в графовой бд хоть и отличается, но вполне усваивается за считанные дни.
joinjoinjoinjoin*join делается суперэффективно и время исполнения таких запросов не зависит от объёма данных (зависит только от количества инциндентных рёбер того же типа). Это достигается за счёт хранения локальных индексов (в графовой бд в каждой вершине есть свой набор индексов, позволяющий эффективно отбирать соседей). Вот тут приведено исследование авторов TitanDB на эту тему и то, как они в своей БД её решают http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/
А какая аналитика тебя интересует?
Михаил Павлов
27.12.2015 в 23:09я бы хотел послушать твой доклад , если он есть у тебя, очень интересно.
я не сейчас могу выделить время на изучение всех этих вещей, лчень уж серьезно надо засесть — камни собирать пора, а то я слишком много разбросал.
возможно открою для себя после этого целый новый пласт алгоритмов?!
> какая аналитика интересует?
не могу сказать. я бы хотел сделать на основе этой штуки основу и решить на ней свои задачи, создав систему «СУП», мы так её называем. далее я открываю API к системе для внешних сервисов. им понадибится возможно данные в разных формах, не обязательно как я дам.
я бы хотел гибкость здесь.
внешние сервисы будут клепать новые представления и конечно хочется чтобы не они придумывали как сделать индекс и по нему строить. а использовать максимально наш функционал для получения данных.
Роман
16.01.2016 в 19:51Мало что сделанное слишком общим, хорошо работает на всех задачах. Наверное, имеет смысл либо использовать sql-решение, поддерживающее запуск на нескольких узлах (а вообще, каков объём данных предполагается на один сервис в среднем? может быть проще предложить несколько вариантов хранилища, как это делает amazon?), либо предложить разработчикам сервисов конструктор, который будет строить схему БД за них.
Кстати, для кассандры есть ещё какой-то ORM: https://cqlengine.readthedocs.org/en/latest/
Про ничего не могу сказать, я использую официальный драйвер с cql
Михаил Павлов
18.01.2016 в 16:35мне этот «ORM» Серега Алексеев показывал. там промитивно внутри все. не знаю пока я не склонен юзать его. а уж как он — это его дело.
мы тожеифициальный драйвер используем. смотри кстати последний мой пост от вчера/позавчера. про стыковку CQL + Thrift.
Кстати в G+ я постил про выход нового бешеного крутого релиза PG.
который опять не подвел ожидания.
Роман
18.01.2016 в 16:54В том посте про cql+thrift не сказано самое главное: зачем это нужно? Если для интроспекции, то гораздо лучше организовать дополнительное хранилище метаинформации, пусть в той же кассандре. Других идей по поводу применения этого гибрида что то не приходит в голову.
Михаил Павлов
20.01.2016 в 10:31> В том посте про cql+thrift не сказано самое главное: зачем это нужно?
Мне нравится Low level api, он позволяет поверх внешних по отношению к касандре сервисов организовать «свой CQL».
Родной CQL не имеет Join и вообще ограничен. ORM опять же слаб — не то слово.
Можно конечно строить новый CQL поверх CQL, собст…но. Но Low level API позволяет потенциально куда больше.
Для выгрузки данных опять же — очень удобно, практически в потоковом режиме можно данные гнать.
Реально, я проверил их оба и решил «использовать только CQL, по крайней мере пока. А Low level хоть и гибкий — в таком виде, как он сейчас есть, смысла не имеет для нас»
Роман
20.01.2016 в 11:31Thrift — deprecated, это значит, что его нельзя использовать в новых проектах. А Join в Cassandra — признак плохого дизайна базы. Используй иерархические ключи, это эффективно и естественно для неё. Соединение разных таблиц, если всё-таки оно нужно, гораздо лучше имитировать на клиенте, т.к. есть возможность эффективнее использовать асинхронные возможности драйвера, IMHO.
Роман
20.01.2016 в 11:33CQL очень хорошо спроектирован: он позволяет ровно то, что позволяет внутренее устройство кассандры. Если что-то CQL не позволяет, то это либо знак, что не надо это делать с помощью кассандры, либо надо попробовать перепроектировать БД, вынеся минимальную логику на клиентскую часть.