Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 110
Неплохо. Надо испробовать у себя…
В IBM (и не только ibm и ms тоже было замечено) иерархию реализовали так
path id, id1, id2, id3…
Очень легко и просто, единственный недостаток — избыточность данных, хотя не особо она избыточна, если присмотреться, зато плюсов очень много. Первое — скорость, вторая легкость, равномерность нагрузки и еще куча вкусностей.
И уже все давно реализовано, причем в полностью законченных видах.
path id, id1, id2, id3…
Очень легко и просто, единственный недостаток — избыточность данных, хотя не особо она избыточна, если присмотреться, зато плюсов очень много. Первое — скорость, вторая легкость, равномерность нагрузки и еще куча вкусностей.
И уже все давно реализовано, причем в полностью законченных видах.
Про пример в лоб- если добавить к cherry потомка надо будет изменить данные для 11 элементов? Для холиваров в комментах такая система будет несколько накладной)
Почитал и понял, что так и есть. Я сам его использую: четыре разряда на уровень = до 10000 элементов, быстрые выборки и элементарный доступ к родителям. Как-то приятнее оно мне MPath
Хороший способ реализации, но если приходится ковырять данные вручную, часто возникает желание застрелиться. Ещё из минусов — добавление 1 узла может привести к обновлению всех узлов в дереве.
Да, штука очень своеобразная. На самом деле в неизменном виде довольно мало применимая, на мой взгляд. Nested Intrvals лучше, но тоже на любителя.
Кстати, вот пачка слайдов по деревьям. Когда-то на хабре проскакивала. Позволяет быстро ознакомится с основными концепциями.
Кстати, вот пачка слайдов по деревьям. Когда-то на хабре проскакивала. Позволяет быстро ознакомится с основными концепциями.
Идеально для чтения, фигово для добавления. Хотя можно сюда же, к Left/Right, добавить классическое id/pid и будет самое оно. Обновлять данные L/R по job'у
Большой недостаток — безопастность данных, затраты на перерасчет.
Лучше id, id1, id2, id3
Лучше id, id1, id2, id3
Отчего бы тогда не сделать восемь полей? Будет значительно быстрее и проще.
А комментаторы восьмого уровня будут неоспоримыми by design :)
А комментаторы восьмого уровня будут неоспоримыми by design :)
Мне очень не нравилась перспектива рекурсии и множество мелких запросов к базеВполне адекватный вариант — когда одним нормальным запросом выбираются все комментарии, а сортировка в нужном порядке делается рекурсией, или даже циклом (рекурсия тут в цикл легко разворачивается). В таком виде это не будет иметь ограничений на уровни и кол-во комментариев на них.
Вы не для free-lance.ru писали?:) Там тоже уровни комментариев ограничены, из-за чего при длительном обсуждении начинается каша и непонятно кто кому отвечает. Очень неудобно на практике.
Ну мне хотелось именно выгребать в готовом виде всё сразу из базы, такая идея фикс.
Нет, я писал для своего блога на GAE, что-то там пока больше двух ответов редко бывает :)
Много ответов всегда сложно читать, вариант который предлагает тот же lj ещё хуже, например.
Нет, я писал для своего блога на GAE, что-то там пока больше двух ответов редко бывает :)
Много ответов всегда сложно читать, вариант который предлагает тот же lj ещё хуже, например.
>Ну мне хотелось именно выгребать в готовом виде всё сразу из базы
>там пока больше двух ответов редко бывает :)
а зачем тогда вообще хранить комментарии отдельными экземплярами модели и их как-то искать?
>там пока больше двух ответов редко бывает :)
а зачем тогда вообще хранить комментарии отдельными экземплярами модели и их как-то искать?
А использовать хранимые процедуры не пробовали?
буквально на прошлой неделе реализовывал хранение комментариев и их вывод, точно так и сделал, думаю самый оптимальный вариант, никаких ограничений, все просто и логично
Как вариант можно иметь два поля, одно позволяет сортировать по уровням, а второе — по-порядку. Тогда ограничение на количество комментариев на одном уровне снимается.
А как вычислять то поле которое «по порядку»? У меня вот для него этот хэш и есть, вроде бы. Из него на самом деле видно и уровень, но я его в явном виде ещё храню, чтобы не делать лишних «вычислений».
Да, вы правы — так не получится. При вставке нового комментария придется переписывать всю таблицу.
Комментарии добавлять хранимой процедурой.
Перед добавлением вычислять два поля: уровень (определяется как уровень родителя + 1) и порядок (вычисляется как максимальный порядок комментария того же родителя + 1).
Вопрос целостности данных, конечно, придется решать дополнительными средствами.
Перед добавлением вычислять два поля: уровень (определяется как уровень родителя + 1) и порядок (вычисляется как максимальный порядок комментария того же родителя + 1).
Вопрос целостности данных, конечно, придется решать дополнительными средствами.
уровень хранить в отдельном поле, порядок — дата/время создания записи
приходила в голову подобная идея. до реализации дело не дошло, но концепция та же. даже больше того приходило в голову несколько идей, как с дополнительным полем, которое фактически может выполнять функцию и первичного ключа, в котором хранится некоторая информация по порядку вложенности элемента.
опять же зависит и от сумой СУБД, так как в Oracle, к примеру, можно реализовать через систему вложенных таблиц, или те хе объекты в полях таблиц. на самом деле все зависит от средств разработки. можно в пустую при каждом комментарии индексировать все дерево комментариев на предмет правильно постановки, а уже выдачу вести из этого индекса.
опять же зависит и от сумой СУБД, так как в Oracle, к примеру, можно реализовать через систему вложенных таблиц, или те хе объекты в полях таблиц. на самом деле все зависит от средств разработки. можно в пустую при каждом комментарии индексировать все дерево комментариев на предмет правильно постановки, а уже выдачу вести из этого индекса.
Правильно ли я понимаю, что вам это нужно для того, чтобы выдергивать произвольные ветки обсуждения, для подгрузки аяксом? Ибо если комментарии отображаются все сразу — не вижу преимуществ перед следующей схемой:
Храним идентификатор комментируемой сущности, идентификатор комментария (AI), идентификатор родителя (0 для комментариев первого уровня).
Для получения всех комментариев к записи выбираем по идентификатору сущности, потом в цикле строим дерево ($comments[$currentComment['parentId']]['childs'][] = &$currentComment;) и отдельный массив со ссылками на комментарии первого уровня. Вам в этом смысле чуть проще разбирать дерево, но запрос будет сложнее. Я не прав?
Храним идентификатор комментируемой сущности, идентификатор комментария (AI), идентификатор родителя (0 для комментариев первого уровня).
Для получения всех комментариев к записи выбираем по идентификатору сущности, потом в цикле строим дерево ($comments[$currentComment['parentId']]['childs'][] = &$currentComment;) и отдельный массив со ссылками на комментарии первого уровня. Вам в этом смысле чуть проще разбирать дерево, но запрос будет сложнее. Я не прав?
Идеи доставать отдельно ветки не было (хотя можно это сделать, нужно будет делать запрос с двумя условиями по хешу).
Строить дерево на клиенте… ну фиг знает, что-то в этом есть порочное ;)
Строить дерево на клиенте… ну фиг знает, что-то в этом есть порочное ;)
На клиенте? В смысле на сервере, который клиент мускуля?
Ну вы же тоже будете строить дерево, разве нет? По мне
Ну вы же тоже будете строить дерево, разве нет? По мне
Прощу
Да е-мое! Прошу прощения.
Я зачем-то жму Ctrl-enter и промахиваюсь мимо бекспейса. Простите ради бога.
Так вот. По мне — лучше нагрузить application-сервер, чем сервер баз данных. А если вы хотите получать комментарии сразу в том порядке, в котором они должны идти, избавляясь от необходимости строить дерево — тогда да, соглашусь, nested sets еще хуже, если нет задачи постоянно тягать ветки)
Так вот. По мне — лучше нагрузить application-сервер, чем сервер баз данных. А если вы хотите получать комментарии сразу в том порядке, в котором они должны идти, избавляясь от необходимости строить дерево — тогда да, соглашусь, nested sets еще хуже, если нет задачи постоянно тягать ветки)
Да, «задача» была именно такая. Хотя совершенно не факт, что это экономически наиболее эффективный путь, так как на вычисление этих хешей я тоже что-то трачу ведь.
Ну тут вопрос активности обсуждения. Если просмотров больше чем добавления комментариев — ваш путь быстрее все-таки)
Кстати, я понял. Вы фактически используете те же самые nested sets, только с большииим запасом. Поскольку вам наплевать на пересечение диапазонов комментариев первого уровня («отступ» вы все равно храните) — вы можете делать тот же самый запас на nested sets, и выиграть в скорости за счет сортировки по числовому, а не текстовому полю.
Ну да, на клиенте, который http-сервер. GAE за лишние вычисления будет лишние ресурсы процессора начислять.
Я дерево как бы не строю, я тупо показываю всё отсортированным по хешу с отступом равным полю «отступ», дерева как бы и нет, только в виде абстракции и резервных ссылок на родителей.
Я дерево как бы не строю, я тупо показываю всё отсортированным по хешу с отступом равным полю «отступ», дерева как бы и нет, только в виде абстракции и резервных ссылок на родителей.
для выдёргивания отдельных веток весьма эффективно хранить список всех предков просто в списочном проперти, и выбирать всех потомков охапкой Query(Comment).filter('ancestors =', top)
Это да. Я вообще в последнее время от фундаментализма нормализации склоняюсь к денормализации, заметно упрощает жизнь. Ну в разумных, конечно, пределах.
к датасторе нормализация не особо применима — оно не реляционное нифига.
Ну я немного в курсе, но лишние данные дублировать не очень люблю, хоть и нереляционное. И в реляционных, с которыми иногда работаю стал немножко денормализовывать по-тихому, пока студенты не видят.
Если рассматривать её в «бытовом» смысле слова (исключение дублирования данных и т. п.), то вполне применима.
Таки речь идет о «материализованном пути», в бинарном представлении.
О, видимо да. Некоторая модификация и, по-моему, не бинарное представление.
Всегда приятно самому изобрести действующий велик!
Всегда приятно самому изобрести действующий велик!
Работающий вел — это на котором можно неспеша лисапедить, а не жостко педалить) В данном случае он как не очень масштабируется на произвольное количество камментов)
А покажите мне блог, где больше 2500 комментариев? И я соглашусь сделать трёхразрядными счётчики, придётся исправить ровно один символ в дефайнах.
Тут два ограничения:
1. достаточно переполнить один уровень ирархии — обычное дело, когда комментарии вырождаются в проский набор, для этого алгоритма;
2. глубина рекурсии в данном примере ограничена тремя — это жесть с точки зрения любого уважающего себя троля.
1. достаточно переполнить один уровень ирархии — обычное дело, когда комментарии вырождаются в проский набор, для этого алгоритма;
2. глубина рекурсии в данном примере ограничена тремя — это жесть с точки зрения любого уважающего себя троля.
Попробуйте что ли прочитать текст статьи?
пробовал, там несколько вариантов изложено — а память запомнает лишь самое доступное)
Вот как понять, вы сперва пишете: «все хранится на третьем уровне — и четвертый, и пятый, и десятый».
И тут же «Развивая эту идею, от цифрового поля я решил отказаться в пользу текстового» — но тут ведь нет явного отрицания уже сказанного. И вообще труЪ-программисты предложения содержащие «тут есть одна хитрость» и все рядом с ним не читают даже по диагонали)
Вот как понять, вы сперва пишете: «все хранится на третьем уровне — и четвертый, и пятый, и десятый».
И тут же «Развивая эту идею, от цифрового поля я решил отказаться в пользу текстового» — но тут ведь нет явного отрицания уже сказанного. И вообще труЪ-программисты предложения содержащие «тут есть одна хитрость» и все рядом с ним не читают даже по диагонали)
такие количества комментариев вполне бывают сами знаете у кого.
раз в месяц, кажется.
раз в месяц, кажется.
ваш метод называется materialized path
CONNECT BY в Oracle, если не ошибаюсь, самое оно.
Как то так:
А с подкомментария №100 начинается веселье.
...
00101 1.1.1 (подкомментарий №1)
...
00199 1.1.99 (подкомментарий №99)
А с подкомментария №100 начинается веселье.
Скажите, а чем и почему ограничено количество уровней?
Ой.
Плохо соображаю под конец дня, но кажется вы очень толковый вопрос задали, спасибо. Непременно отчитаюсь отдельно об этом.
Плохо соображаю под конец дня, но кажется вы очень толковый вопрос задали, спасибо. Непременно отчитаюсь отдельно об этом.
В общем начиналось всё с числового этого «пути», то есть были бы пути в духе тех, что я написал в примере 010000 и подобные. Чтобы работала сортировка, я, конечно, должен добивать нумерацию на нулевом уровне нулями на младших разрядах, чтобы 02 не оказалась раньше 010101, например.
Так как длина числа ограничена и это всего 10 значений на знакоместо, я перешёл на буквы, то есть та самая система счисления с основанием 50. Но буквы сортируются не по значению, а алфавитно и получается что добивать нулевыми разрядами ничего не надо, то есть ac всегда будет идти после ababab, например.
Вложенность остаётся ограниченной просто длиной текстового поля отведённого под этот хеш, вот. Надо попробовать проверить этот вариант на практике, чего лишние буквы хранить.
Так как длина числа ограничена и это всего 10 значений на знакоместо, я перешёл на буквы, то есть та самая система счисления с основанием 50. Но буквы сортируются не по значению, а алфавитно и получается что добивать нулевыми разрядами ничего не надо, то есть ac всегда будет идти после ababab, например.
Вложенность остаётся ограниченной просто длиной текстового поля отведённого под этот хеш, вот. Надо попробовать проверить этот вариант на практике, чего лишние буквы хранить.
В постгресе есть замечательные запросы WITH RECURSIVE которые позволяют выгребать рекурсивно деревья.
Вот красивая статейка на эту тему — explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/
Вот красивая статейка на эту тему — explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/
а нафига на GAE так танцевать? храним все комментарии в одном entity в пикле и не чешемся вообще.
можно принтскрин графиков нагрузки с админки?
А там ничего особенно интересного, про нагрузку я отдельно писал, там и графиков побольше.
Сейчас нагрузка по заходам меньше чем в тот раз была.
Сейчас нагрузка по заходам меньше чем в тот раз была.
Зачем так усложнять? Почему нельзя просто выбрать одним запросом все комметраии, и вывести их одним циклом?
Traceback (most recent call last):
File "/base/python_runtime/python_lib/versions/1/google/appengine/ext/webapp/__init__.py", line 702, in __call__
handler.post(*groups)
File "/base/data/home/apps/dgwnpgnd/1.350986457899533822/comment.py", line 491, in post
text = process_comment(self.request, True)
File "/base/data/home/apps/dgwnpgnd/1.350986457899533822/comment.py", line 569, in process_comment
bgrec = basecmnt.blogrec
AttributeError: 'NoneType' object has no attribute 'blogrec'
что-то у вас сломалось…
File "/base/python_runtime/python_lib/versions/1/google/appengine/ext/webapp/__init__.py", line 702, in __call__
handler.post(*groups)
File "/base/data/home/apps/dgwnpgnd/1.350986457899533822/comment.py", line 491, in post
text = process_comment(self.request, True)
File "/base/data/home/apps/dgwnpgnd/1.350986457899533822/comment.py", line 569, in process_comment
bgrec = basecmnt.blogrec
AttributeError: 'NoneType' object has no attribute 'blogrec'
что-то у вас сломалось…
Посоветуйте, как разбивать вложенные комментарии на страницы (комментариев в теме бывает более 500 и выводить их на одной странице — убийственно просто).
В моём случае как раз решается легко: по порядку, плюс аяксом подгружать вниз. То есть вот select from comments where blogpost = :1, order by hash, limit 500. В случае с GAE правда будет небольшой косяк с limit 500 (он не умеет), но обходится легко как раз с помощью монотонно растущего hash.
Хм… а если страница вторая и комментариев более второго уровня больше, чем 500, среди которых есть и новые и старые. И таких тем 50-60. Как бы Вы отобразили это, чтобы пользователю было понятно, где он находится и к чему каждый комментарий?
когда комментариев второго уровня больше чем страница, пользователю-читателю уже пофиг.
а пользователи-писатели и так разберутся, по ссылкам в имэйл-уведомлениях :)
а пользователи-писатели и так разберутся, по ссылкам в имэйл-уведомлениях :)
Для начала я бы давал «листать» аяксом, продолжая вниз, не потеряешься. Проблемы найти комментарий первого уровня для любого заданного дочернего нет, это будет комментарий с хэшем с обнулённым хвостом, можно начинать страницу всегда с таких. Это всё довольно легко решается при таком подходе по-моему.
а исходники livejournal, например, случайно не opensource?
В lj одна из самых медленных и некрасивых реализаций комментариев, уж я не знаю что причиной, миллиарды комментаторов или таки кто-то пытался решать проблему «в лоб». Кстати у них ещё и какое-то смешное ограничение на количество комментариев к одному посту есть.
а чем оно некрасиво?
Чисто внешне: что ли можно это читать? Всего 200 комментариев, а превратилось в целый квест.
а что там не так?
— пэйджатся камменты первого уровня (чтобы на странице не оставался только хвост)
— длинные ветки сворачиваются.
чем вам это кажется ужасным и какие альтернативные формы выдачи флэймов на ваш взгляд более удобны?
я бы, конечно, глубину сворачивания чуть побольше сделал, чтобы тема углубления очевиднее была.
ну и подгружал/скрывал бы их аяксом, также как и сами страницы.
— пэйджатся камменты первого уровня (чтобы на странице не оставался только хвост)
— длинные ветки сворачиваются.
чем вам это кажется ужасным и какие альтернативные формы выдачи флэймов на ваш взгляд более удобны?
я бы, конечно, глубину сворачивания чуть побольше сделал, чтобы тема углубления очевиднее была.
ну и подгружал/скрывал бы их аяксом, также как и сами страницы.
Читать комментарии когда начались сворачивания просто вообще нельзя. Это и не нравится, никто и не читает. Expand этот клёвая штука, но медленный до ужаса.
Мне куда больше нравятся варианты хабра и лепры/дёти, надо думать и то и другое футурико основали, так и остаётся. И там (на лепре) бывает за тысячу комментариев, ну тяжеловато открывается, да… Можно придумывать страницы; самое соблазнительное, конечно, — нарезать по комментариям первого уровня. Причём GAE как раз будет мотивировать ограничивать не по комментариям первого уровня.
Кстати бесконечная вложенность, именно визуальная, приводит к комментариям шириной в 50 точек на хабре — не лучший вариант. Это была одна из идей, из которых я исходил вообще — ограничить вложенность по крайней мере визуально.
Мне куда больше нравятся варианты хабра и лепры/дёти, надо думать и то и другое футурико основали, так и остаётся. И там (на лепре) бывает за тысячу комментариев, ну тяжеловато открывается, да… Можно придумывать страницы; самое соблазнительное, конечно, — нарезать по комментариям первого уровня. Причём GAE как раз будет мотивировать ограничивать не по комментариям первого уровня.
Кстати бесконечная вложенность, именно визуальная, приводит к комментариям шириной в 50 точек на хабре — не лучший вариант. Это была одна из идей, из которых я исходил вообще — ограничить вложенность по крайней мере визуально.
Я также такой способ использовал для хранения комментариев, только для хранения хеша использовал поле blob, и все ASCII символы, тогда один байт мог содержать 256 позиций, 2 байта — 65536, и так дальше…
В хранилище GAE хранение дерева «из коробки» и все комменты к посту выбираются выборкой этого поста. Или есть ограничения на размер одного объекта?
кто ещё не читал…
Joe Celko's Trees and hierarchies in SQL for smarties
скачать в PDF на варезниках не проблема
Joe Celko's Trees and hierarchies in SQL for smarties
скачать в PDF на варезниках не проблема
SQL и гугловский BigTable — две большие разницы. В частности выборка сущностей, находящихся в отношении композиции с основной «таблицей» операция более дешевая вроде как. Сущностей, находящихся в отношении агрегации — более дорогая. А уж выборка «внешней» сущности (контейнера) по «внутренней» — очень дорогая.
В данном случае хэш содержит как бы три двузначных разряда: комментарии нулевого уровня нумеруются в двух первых разрядах, второго в двух вторых и так далее.
Хэши, блин.
Битовые (bitwise) операции (как упаковать 2 16-битных числа в одно 32-битное и т.п.) значит уже все забыли? %)
поддерживает ли Ваша структура данных изменения? Напр., перенос ветки обсуждения в другую «тему» (если представить, что мы имеем дело с форумом).
В нашей web студии давно работает полностью иерархическая cms, и уже очень давно.
Плюсов очень много, на порядок проще b быстрее любой обьектной cms.
Плюсов очень много, на порядок проще b быстрее любой обьектной cms.
А можете привести пример популярной объектной CMS. Мне всё как-то больше иерархические попадаются, пускай даже не с одним уровнем иерархии. Самая близкая к объектной, имхо, Drupal, но и там «мышкой» нельзя (7-ку не смотрел) построить модель предметной области, если она не вписывается в таксономию.
Популярной иерархической open source CMS — нет, только закрытые. :\
Практически все обьектные, в той или иной мере, там архитектура далека от иерархии. Какие иерархические вам попадаюся?
Практически все обьектные, в той или иной мере, там архитектура далека от иерархии. Какие иерархические вам попадаюся?
Хотя бы закрытой. Что-то там в ГК есть личные и исследовательские цели ;)
То есть все позволяют в той или иной степени создавать пользователю новые типы данных (классы объектов) и их экземпляров (объекты), создавать им новое поведение, наследовать один тип от другого и изменять поведение родителя. произвольно (а не только иерархически) связывать один объект с другим?
То есть все позволяют в той или иной степени создавать пользователю новые типы данных (классы объектов) и их экземпляров (объекты), создавать им новое поведение, наследовать один тип от другого и изменять поведение родителя. произвольно (а не только иерархически) связывать один объект с другим?
Изобретать вилосипед полезно и интересно. Но есть же Adjacency List, Materialized Path, Nested Sets (упомянутые выше). Все это замечательно работает под определенными задачами и имеет множество готовых реализаций…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Хранение иерархических данных в плоском виде