VD>Вообще-то B+ отличаются очень незначительно. Это небольшое усовершенствование. Просто связали страницы двунаправленным списком и все. Оно и в памяти удобнее.
Да в курсе мы чем B от B+ отличаются
Я пытался сказать что в памяти эти указатели для двунаправленного списка избыточны — найти предыдущую-следующую страницу несложно, благо латентности у памяти небольшие. А вот для диска это уже существенно — лишнее обращение к диску стоит дорого.
Здравствуйте, Left2, Вы писали:
L>Я пытался сказать что в памяти эти указатели для двунаправленного списка избыточны — найти предыдущую-следующую страницу несложно, благо латентности у памяти небольшие.
Ошибашся. Промежуточные страницы они в принципе в память сразу попадают. Тут в другом дело. Вдло в упрощении сканирования. Алгоритм превращается линейный перебор.
L> А вот для диска это уже существенно — лишнее обращение к диску стоит дорого.
Не будет там никаких лишних обращений. Когда ты переходишь к одной из нижних страниц ты обязан поднять в память корневую страницу. Просто при переборе ты не будешь лазить по дереву, сразу начнешь сканирование записей.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Вообще-то B+ отличаются очень незначительно. Это небольшое усовершенствование. Просто связали страницы двунаправленным списком и все.
Нет, не все. В В+ дереве, кроме того, все элементы храняться в листьях (иначе было бы бессмысленно делать указатели на соседние листья).
Здравствуйте, Left2, Вы писали:
AVK>>RB деревья как раз используются при необходимости. А вот В+ в реальных проектах я не видел ни разу.
L>Symbian OS — в стандартной библиотеке есть реализация B-деревьев. IMHO, переходить от B к B+ имеет смысл только если они лежат на диске — для работы с памятью B-деревья предпочтительнее B+.
А чем обосновано данное утверждение??? В зависимости от типа КеуValuePair, и количества элементов на странице процент лишней памяти весьма незначителен, а вот выигрыш при чесе по страницам весьма заметен. Да и реализация немного проще.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, AndrewVK, Вы писали:
AVK>Нет, не все. В В+ дереве, кроме того, все элементы храняться в листьях (иначе было бы бессмысленно делать указатели на соседние листья).
Ага. Вот только это все равно не влияет на использование их в памяти. Просто более совершенная разновидность алгоритма.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Left2, Вы писали:
L>Сильно сомневаюсь что это хорошая идея — хранить данные на диске через хеш-таблицу. Слишком медленным получится последовательное чтение — поскольку прийдётся скакать случайным образом по всей таблице.
Именно поэтому хеш-индексы сейчас малопопулярны. Дело в том, что редкий оптимизатор в силах угадать способ доступа. Тем не менее, они все же применяются — там, где можно заранее определить назначение некоторого индекса. К примеру, FK-индексы как правило используются только для lookup, а lookup по хеш-таблице имеет более мягкую асимптотику, чем по дереву. L> Хотя, может для каких-то специфических задач это и прокатит... Впрочем, при добавлении в RB-дерево случайным образом страницы тоже могут перемешаться на диске
Не знаю насчет RB-деревьев; для B/B+/B* деревьев все операции требуют log(N) времени, и с учетом очень вероятного кэширования рута и первого уровня дерева этот логарифм превращается в подкачку ровно 1 страницы в 95% случаев. L>- но тут по крайней мере можно слегка прогнуться и сделать дефрагментацию, а вот хеш-таблицу ничто не спасёт
Я думаю, тебе стоит почитать учебники по проектированию СУБД. Там описаны алгоритмы хеш-индексов, пригодные для дисковых операций.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
C>>Ну да, можно положить Assemblt в GAC и сделать ей ngen'ом C>>оптимизированое изображение.
AVK>Афигеть. Блин, ну ты и спорщик. AVK>Для того чтобы обработать ngen'ом сборку не нужно класть ее в GAC. Единственная связь между GAC и ngen это то что каталог ngen'а лежит рядом с каталогом GAC.
Здравствуйте, VladD2, Вы писали:
VD>Ага. Вот только это все равно не влияет на использование их в памяти.
Влияет на использование на диске. В+ дерево в реальности стараются хранить так, чтобы соседние страницы лежали последовательно друг за другом. Это минимизирует количество перемещений головки при выборе диапазона. Для вариантов в памяти это, естественно, никто не делает.
Здравствуйте, Sinclair, Вы писали:
S>Я думаю, тебе стоит почитать учебники по проектированию СУБД. Там описаны алгоритмы хеш-индексов, пригодные для дисковых операций.
А такой есть?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
L>>- но тут по крайней мере можно слегка прогнуться и сделать дефрагментацию, а вот хеш-таблицу ничто не спасёт S>Я думаю, тебе стоит почитать учебники по проектированию СУБД. Там описаны алгоритмы хеш-индексов, пригодные для дисковых операций.
Хай Бог Мылуе В ближайшее время проектированием СУБД заниматься не собираюсь Их вроде бы и так выше крыши на рынке — выбирай любую по вкусу и цене
Я уже пытался обьяснить — изначально-то разговор шёл не о написании более-менее честной СУБД а о подтачивании стандартных (ну, или околостандартных ) контейнеров C++ для хранения данных на диске.
Здравствуйте, AndrewVK, Вы писали:
AVK>Влияет на использование на диске. В+ дерево в реальности стараются хранить так, чтобы соседние страницы лежали последовательно друг за другом.
Стараться конечно можно. Вот только по жизни это может вызвать копирование всего содержимого индекса.
И В-дерево тут ничем не отличается. Еше раз повторяю, что В+-дерево — это всего лишь небольшая оптимизация В-дерева. В основном характеристики у них одинаковые. Приемущество В+-дерева проявляется только при последовательном сканировании. Причем это приемущество остается независимо от того где распологается индекс.
AVK> Это минимизирует количество перемещений головки при выборе диапазона. Для вариантов в памяти это, естественно, никто не делает.
И что мешат распологать страницы В-дерева последовательно?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
AVK>>Влияет на использование на диске. В+ дерево в реальности стараются хранить так, чтобы соседние страницы лежали последовательно друг за другом.
VD>Стараться конечно можно. Вот только по жизни это может вызвать копирование всего содержимого индекса.
Может. Техника борьбы стандартная — оставлять запас для роста.
VD>И В-дерево тут ничем не отличается.
Отчасти отличается. Там понятие соседняя страница не так очевидно (потому как данные не только в листьях). Ну и главное — в тех деревьях, которые храняться в памяти, В или В+ не важно, такая оптимизация отсутствует.
VD>Приемущество В+-дерева проявляется только при последовательном сканировании.
Я про последовательное сканирование и говорю.
VD> Причем это приемущество остается независимо от того где распологается индекс.
На диске зависит.
VD>И что мешат распологать страницы В-дерева последовательно?
Как ты расположишь страницы В дерева последовательно, если данные есть и в родительской странице и в дочерних?
Здравствуйте, AndrewVK, Вы писали:
AVK>Как ты расположишь страницы В дерева последовательно, если данные есть и в родительской странице и в дочерних?
Последовательно. Я тебе уже говорил, что никто не будет это делать в реальных приложениях, так как это приведет к пересозданию индекса. На то есть разные отдельные процедуры оптимизации. А обычно работе если индекс вырос, то новая страница выделяется там где получится.
В общем, ты не прав. В-деревья изначально разрабатывались для хнанения на дисках. B+ конечно лучше. Но это не более чем оптимизация исходного алгоритма.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Left2, Вы писали:
L>Я уже пытался обьяснить — изначально-то разговор шёл не о написании более-менее честной СУБД а о подтачивании стандартных (ну, или околостандартных ) контейнеров C++ для хранения данных на диске.
Ну, вот тебе и посоветовали не маяться дурью. Но ты похоже это не осознал.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
L>>Я уже пытался обьяснить — изначально-то разговор шёл не о написании более-менее честной СУБД а о подтачивании стандартных (ну, или околостандартных ) контейнеров C++ для хранения данных на диске.
VD>Ну, вот тебе и посоветовали не маяться дурью.
Посоветовали не использовать Hashtable и подобные Hashtable контейнеры для хранения на диске. Ну и ладно, в boost'е уже есть File-Mapping-аллокатор (Shmem), появится и boost::btree.
1.1.4 stable rev. 510
) контейнеров C++ для хранения данных на диске.
