Добрый день, есть структура данных полученная выборкой из БД иерархической структуры, пусть будет Город-Район-Устройство, обозначим их для простоты числовыми значениями. Получаем набор кортежей, я так понимаю они не обязательно должны быть упорядочены

1 1 1
1 1 2
1 2 3
1 3 3
2 4 6
2 4 7
2 4 8
3 5 9
1 5 6

Должно получиться

1-|
  1-|
    1
    2
  5-|
    6
  2-|
    3
2 
  4-|
    6
    7
3
  5-|
    9

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

Здравствуйте, da17, Вы писали:

D>Вопрос заключается вот в чем, на мой взгляд задача похожа на стандартную и мне кажется ей уже название придумали или надо самостоятельно решать? Интересуюсь в плане быстродействия, т.к. дерево получается порядка нескольких тысяч узлов.

Порядка нескольких тысяч узлов — это копейки.
Если только речь не о "нескольких тысяч узлов в миллисекунду".

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, da17, Вы писали:

D>>Вопрос заключается вот в чем, на мой взгляд задача похожа на стандартную и мне кажется ей уже название придумали или надо самостоятельно решать? Интересуюсь в плане быстродействия, т.к. дерево получается порядка нескольких тысяч узлов.

К>Порядка нескольких тысяч узлов — это копейки.
К>Если только речь не о "нескольких тысяч узлов в миллисекунду".

Да я начал сперва в лоб решать, одним SELECT выбрал родителей, затем в цикле выбрал для каждого родителя потомков, пока было 500 узлов все работало отлично, когда стал переходить от модели к рабочему прототипу, все стало занимать порядка 70 секунд, решил выбирать с БД данные одним селектом.

Здравствуйте, da17, Вы писали:

D>Да я начал сперва в лоб решать, одним SELECT выбрал родителей, затем в цикле выбрал для каждого родителя потомков, пока было 500 узлов все работало отлично, когда стал переходить от модели к рабочему прототипу, все стало занимать порядка 70 секунд, решил выбирать с БД данные одним селектом.

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

Здравствуйте, da17, Вы писали:

D>Добрый день, есть структура данных полученная выборкой из БД иерархической структуры, пусть будет Город-Район-Устройство, обозначим их для простоты числовыми значениями. Получаем набор кортежей, я так понимаю они не обязательно должны быть упорядочены
D> ...
D>Вопрос заключается вот в чем, на мой взгляд задача похожа на стандартную и мне кажется ей уже название придумали или надо самостоятельно решать? Интересуюсь в плане быстродействия, т.к. дерево получается порядка нескольких тысяч узлов.

Если нужно будет делать подвыборки, вида "дай мне все устройства в Городе-Районе", то дерево для этой задачи будет самое то. Несколько тысяч узлов это не много.
Если подвыборок делать не надо, а просто хочется получать набор данных для "Город-Район-Устройство", то можно использовать хэштаблицу.

Здравствуйте, da17, Вы писали:

D>Добрый день, есть структура данных полученная выборкой из БД иерархической структуры, пусть будет Город-Район-Устройство, обозначим их для простоты числовыми значениями. Получаем набор кортежей, я так понимаю они не обязательно должны быть упорядочены
D>

D>1 1 1
D>1 1 2
D>1 2 3
D>1 3 3
D>2 4 6
D>2 4 7
D>2 4 8
D>3 5 9
D>1 5 6
D>

D>Должно получиться
D>

D>1-|
D>  1-|
D>    1
D>    2
D>  5-|
D>    6
D>  2-|
D>    3
D>2 
D>  4-|
D>    6
D>    7
D>3
D>  5-|
D>    9
D>

D>Вопрос заключается вот в чем, на мой взгляд задача похожа на стандартную и мне кажется ей уже название придумали или надо самостоятельно решать? Интересуюсь в плане быстродействия, т.к. дерево получается порядка нескольких тысяч узлов.

Многие бд уже поддерживают иерархические запросы. Смотрите доку по своей бд.

Если не хочется делать хеш-таблицу, содержащую хеш-таблицы и бояться анти-хеш атак, то можно:
* Отсортировать кортежи (средствами базы?).
* Идти по ним сверху вниз и строить дерево. Смотрим, какой длины префикс текущего кортежа совпадает с какой длины префиксом предыдущего кортежа. Добавляем все узлы, которые правее совпавшего префикса.

Здравствуйте, da17, Вы писали:
D>Вопрос заключается вот в чем, на мой взгляд задача похожа на стандартную и мне кажется ей уже название придумали или надо самостоятельно решать? Интересуюсь в плане быстродействия, т.к. дерево получается порядка нескольких тысяч узлов.
Непонятно, в чём проблема. Делаете одну выборку, идёте по ней курсором и складываете данные в древовидную структуру данных. Быстродействие добавления в дерево — O(lnN), для структур в памяти оно бесконечно велико по сравнению с временем чтения из БД. Пока размер данных не сравнится с характерным объёмом RAM на вашей машине, беспокоиться не о чем.