2 ну я

>>Хранить их наиболее оптимально с точки зрения доступа в дереве.

Это вы сами так решили ?

Тогда надо бы обосновать.

С точки зрения доступа, например ко всем данным - дерево НИКОГДА не оптимальнее, скажем списка т.к. в дереве нужен какой-никакой алгоритм обхода.

и т.п.

>>s z="^tree" f s z=$q(@z) q:'$l(z) w !,z," ",@z этот алгоритм обхода думаю не сложный и не времязатратный

Издеваетесь ?

Может расскажете что это за алгоритм, а то s z="^tree" f s z=$q(@z) q:'$l(z) w !,z," ",@z как то не очень понятно:) ?

Кроме того в случае полного обхода дерева алгоритм ВСЕГДА НУЖЕН, в случае списка НЕ НУЖЕН, в случае массива ТОЖЕ НЕ НУЖЕН.

2 ну я

>>Да с какого перепугу надо издеваться? Язык такой.
>>Запросы на sql в три-десять экранов - гораздо большее издевательство

именно издеваетесь :)

Читать эти козявки невозможно. Сокрашение нормальных операторов до одной буквы АБСОЛЮТНО ничего не даёт в плане скорости выполнения, зато серьёзно затрудняет чтение. При помощи какого-нибудь препроцессора так исковеркать можно любой язык, только какой смысл - непонятно.

Пояснения это уже изощрённое издевательство :

"взять следующее имя в дереве" - в дереве нет "имён", есть только пары вида Ключ-Значение и вершины(узлы).
"w - записать в текущий девайс (write)" Что за "девайс" ? Надеюсь не на ленту ? Хорошенкий был-бы алгоритм обхода :)
" перевод строки" А он тут каким боком ?
"@z - пойдет значение узла имя которого в переменной z" Помогите ! Спасите ! Узлы (ага ! они таки есть !) пойдут.

Вообщем-то никто не просил вырисовыать козявочек, у нас для этого коллега ЧАЛ имеется. Просто хотел уяснить (без издевательств и ерничанья), как например тут - http://algolist.manual.ru/ds/walk.php каким алгоритмом дерево обходится. В ответ получил "запись в девайс" и "перевод строки"

2 ну я

Да вас никто не просил программу на каком-то языке приводить.

Просили внятно описать АЛГОРИТМ ОБХОДА ДЕРЕВА для которого разница между обходом списка и массива "практически может быть сведена к нулю".

Попросили просто обосновать.

В качестве обоснования повесили соплю s z="^tree" f s z=$q(@z) q:'$l(z) w !,z," ",@z

И дополнили "обяснением" про "запись в девайс" и "перевод строки".

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

Подозрения, похоже справедливы раз вместо ОПИСАНИЯ АЛГОРИТМА советуют выучить какой-то малоизвестный язык программирования.

2 ну я.

>>Мампс оперирует деревьями, которые хранятся в файлах. Файл - это последовательность байт.

Т.е. с rawdevice MUMPS не работает ? :)

>>Для эффективности кеширования файл делится на блоки.

Мне кажется, эффективность тут ни при чём, просто так устроена дисковая подсистема - с ней можно обмениваться только блоками фиксированного размера.
Гораздо эффективнее и проще было-бы работать с фрагментами нужного размера чем с блоками.

>>В каждом блоке файла хранится несколько ключей узлов и / или значений этих узлов.

По другому и быть не может - кроме как в блоке, хранить негде (см. выше).

>>При вставке узла он вставляется всегда в сортированном виде.

Поясните что такое "сортированный вид узла" ?

>>При необходимости блок расщепляется.

В общем в голове восхитительная каша. И при этом хватает смелости делать заявления типа - "... учите матчасть ...".
Так вот, для того что бы дерево именовалась Б-деревом должны выполняться следующие условия :

1. Должен быть определён "корневой блок"
2. В каждом блоке должен находится список ключей К1...Кn такие что K1<=K2<=K3...<=Kn
3. Каждый блок должен содержать признак того является он листом или нет (это необязательно)
4. В каждом блоке, если он не лист, должен находится список ссылок на "дочерние" блоки C1(К1),C2(К2)...Cn(Кn)

Если интересует более детальное описание, откройте Кормена или Кнута, там есть :)

Пока же :

1. Так вот у вас просто "В каждом блоке файла хранится несколько ключей узлов" это раз.
Вы забыли указать, что в каждом блоке ещё и храниться список указателей на "дочерние" блоки.

2. Непонятен случай как быть в случае нескольких блоков ведь "При необходимости блок расщепляется" - в каждом блоке есть ссылка на другой блок или как ?


>>Те же принципы используют и sql реализации при хранении индексов деревянного вида (классический вариант).

Нет не те же. Вы кое-что пропустили.


>>При последовательном проходе по ключам, а это то что выполнял в предыдущем примере проход в цикле с итерацией по $query, выполняет практически линейный проход внутри одного блока.
Вот первый блок закончился и ... что будет если файл занимает несколько блоков ?

>>Практически - означает не в точности, поскольку блоки могут быть расщеплены и при проходе может произойти переход к другому блоку.
КАК ??? ОТКУДА МЫ УЗНАЁМ АДРЕС(СМЕЩЕНИЕ) СЛЕДУЮЩЕГО БЛОКА ?
В каждом блоке хранится адрес следующего блока или ... как ?


>>Вероятность того, что два соседних (в порядке сортировки) ключа лежат в одном блоке достаточно высокая чтобы сделать суждение о практической эквивалентности такого прохода по дереву и прохода по эквивалентному ему массиву.
Вывод совсем неверный ответье на пред. вопрос и поймёте почему, если не поймёте ответ вот он :

Так вот, насколько я смог понять из сбивчивого объяснения и закорючек в которых есть Цикл и Порядок обхода с получением адреса след блока в вашем случае
всё хранится в виде СВЯЗАННОГО СПИСКА. Внутри этого списка есть нек. структуры в виде B*-дерева. (Как всё это согласовывать в многопользовательской среде ?)
Поэтому и сравнивая обход СПИСКА с обходом СПИСКА мы получаем одинаковый результат (удивительно правда).

Всё почти как в современных РСУБД, только там можно хранить B*-дерево отдельно (в виде индекса) а можно хранить Дерево и данные вместе.

У всего есть свои плюсы и минусы :

Раздельное хранение :
+ Индекс можно отключить перед массовой операцией обновления\удаления
+ Может существовать несколько индексов и использоваться будут только необходимые
+ Индекс можно изменять паралелльно со обновлением данных (допуская дисбаланс)
- Накладные расходы при работе с разными объектами (данными и индексами)

Хранение данных и дерева вместе :
+ Нет накладных расходов на отдельное чтение индекса и данных
- Данные всегда должны быть представленные в виде Key-Value
- Массовые операции обновления\удаления всегда будут приводить к расходам на балансировку дерева

Решать разработчику как хранить (в случае соврем. РСУБД), в случае КАШЕ - выбора НЕТ.

Вот и получаем при попытке массовой вставке :

"В частности, была реальная БД по регистрации состояний устройств, (устройство, имя,значение). Причем данные не удалялись а непрерывно росли. Если в начале эксплуатации удавалось записать до 100 состояний в секунду, то через месяц, когда количество обьектов (записей) выросло до неск. сот тысяч, удавалось вставлять максимум 5 состояний в секунда, и это при почти 100% загрузке дисковой подсистемы и CPU!"

Система только и занимается тем , что дерево балансирует.