эффективное хранение дерева во внешней/медленной памяти

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From Russian to

Threaded View
Hемедленно нажми на RESET, All!

  Какие могут быть хоть бы общие подходы к задаче? Если считать,
что доступ к внешней памяти медлителен, кроме того дорогОй
оказывается seek(). Памяти может быть в несколько раз больше чем
нужно. Хотелось бы иметь возможность относительно легко модифицировать
отдельные листья.


эффективное хранение дерева во внешней/медленной памяти
Привет, Kirill !


 06 Mar 05 , 11:21  Kirill Frolov писал к All:

KF>   Какие могут быть хоть бы общие подходы к задаче? Если считать,
KF> что доступ к внешней памяти медлителен, кроме того дорогОй
KF> оказывается seek(). Памяти может быть в несколько раз больше чем
KF> нужно. Хотелось бы иметь возможность относительно легко модифицировать
KF> отдельные листья.

0 - левое поддересво, 1 - правое. составляем 0 и 1, получаем адрес листа либо
запись о том, что такого листа нет.
Если дерево несбалансированное - алгоритм чуть иной будет.

.                                            С уважением, Hикита.
icq:240059686, lj-user:nicka_startcev
... Пересадить собаку с сена на цепь

эффективное хранение дерева во внешней/медленной памяти
Sun Mar 06 2005 11:21, Kirill Frolov wrote to All:

 
 KF>   Какие могут быть хоть бы общие подходы к задаче?

 Посмотри как в Zip-е сделано.

 VLV

 "Быть честным - лучший способ оставаться бедным"  (c) Hаполеон Бонапарт


эффективное хранение дерева во внешней/медленной памяти
Hi Kirill!

В воскpесенье, 06 маpта 2005 11:21:29, Kirill Frolov писал to All:

 KF>   Какие могут быть хоть бы общие подходы к задаче? Если считать,
 KF> что доступ к внешней памяти медлителен, кроме того дорогОй
 KF> оказывается seek(). Памяти может быть в несколько раз больше чем
 KF> нужно. Хотелось бы иметь возможность относительно легко модифицировать
 KF> отдельные листья.

3 том Кнута?

                                                                Sincerely,
                                                                       Vadim.

Re: эффективное хранение дерева во внешней/медленной памяти
Hello, Kirill!
You wrote to All on Sun, 06 Mar 2005 11:21:29 +0300:

 KF>   Какие могут быть хоть бы общие подходы к задаче? Если считать, что
 KF> доступ к внешней памяти медлителен, кроме того дорогОй оказывается
 KF> seek(). Памяти может быть в несколько раз больше чем нужно. Хотелось
 KF> бы иметь возможность относительно легко модифицировать отдельные
 KF> листья.

    Нужно проанализировать какой доступ и по каким параметрам тебе нужен.
_Обычно_ оптимизируют либо обход всего дерева, либо поиск по _одному_ ключу
(в последнем случае дерево чаще всего представляет собой индекс к чему-то
другому, т.е. строится ради этого и вся его структура "заточена" на решение
именно этой задачи). Самым простым представляется вспомогательное индексное
дерево по нужному ключу - неплохо описано у Вирта.
    А вообще - типичная СУБДовская задача, т.е. нужно искать алгоритмы и
идеи там.

With best regards,
Alexander Derazhne



Re: эффективное хранение дерева во внешней/медленной памяти
Hello Kirill.

06 Mar 05 11:21, you wrote to All:

 KF>   Какие могут быть хоть бы общие подходы к задаче? Если считать,
 KF> что доступ к внешней памяти медлителен, кроме того дорогОй
 KF> оказывается seek(). Памяти может быть в несколько раз больше чем
 KF> нужно. Хотелось бы иметь возможность относительно легко модифицировать
 KF> отдельные листья.

а если как dbf по блокам разбросать?
Или так-же по пол-блока, или слитно, но втыкать
кластеры при вставке...

Vladimir


Site Timeline