kiltum (kiltum) wrote,
kiltum
kiltum

Тут я увидел, как решали одну стандартную на мой взгляд задачу.

Дано:
- Обычная база SQL.
- В ней много записей. Очень много записей. 100 миллионов - это так, для разминки.
- Каждая запись имеет свой id.
- Каждая запись имеет parent_id, который ссылается на id родителя.
- Максимальный уровень вложенности цепочки {id-parent_id}-{id-parent_id} известен.

В общем, тупое и простое дерево, которое кто-то положил в базу. Оно работает, но меедленно, ибо запросы к нему идут в духе "на каком уровне вложенности находится такой-то id", "какой id у родителя на 2 уровня выше" или "дай мне всех потомков с такого-то уровня вложенности" ....

С базой можно делать все, что угодно. Индексы строить, поля добавлять, вьюшки делать ... Главное, что бы быстро было, а то запросы долго выполняются, ибо тупо в железо упираются уже :) База в память не лезет, пилить "база отдельно" - "дерево id" нельзя по разным причинам.

Если честно, то я не понял алгоритма, который наворотил народ. Мои попытки "а может вот так лучше" народ проигнорировал с криками "у нас все работает, надо просто быстрее сделать" ... Оставил попытки, ибо вдруг ...

А вы в курсе, как такие задачи решают? :)

Update: после шаренья по инету обнаружил, что такие задачи народ решает практически "в лоб". Ни одного решения из области high-load не нашел после поверхностного гугляжа. Это чего, новая закрытая каста что ли?
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments