алгоритм B-tree

[yana]

алгоритм B-tree

кто подскажет, в B-tree количество операций на вставку и удаление одинаковое?

 

[x-yuri]

вставка и удаление находится в логарифмической зависимости от amortized time (не знаю как точно переводится, среднее время на операцию в худшем случае) (http://en.wikipedia.org/wiki/B-tree)

 

[yana]

у меня есть дерево, и по нему выходит, что кол-во действий на вставку и удаление одинаковое, вот меня и терзают смутные сомнения

 

[x-yuri]

какие? правда это или вымысел?
дерево кстати в пхп? а то я про бд сначала подумал

 

[yana]

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

 

[x-yuri]

ну ты ссылку глянул? там написано, что оба растут по логарифму от одной и той же величины
или источнику не доверяешь?
кстати, это про сбалансированные деревья, у тебя так?

 

[yana]

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

 

[x-yuri]

Сбалансированное дерево - древовидная структура, которая хранит данные отсортированными и позволяет производить поиск, вставку и удаление в логарифмической зависимости от амортизированного времени (среднее время операции в худшем случае)
сбалансированное - когда максимальный путь (от корня до узла) от минимального практически не отличается, для этого периодически должна проводиться балансировка

 

[yana]

ох, ну неужели все так сложно, а счастье было так близко

 

[x-yuri]

не знаю, может кто-нибудь попроще что-то ответит

-~{}~ 23.12.08 12:39:

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

 

[Wicked]

http://algolist.manual.ru/ds/s_btr.php

 

[MiksIr]

Пользуясь случаем... офтопик А мускуль при работе с utf8 работает с символами или байтами? Т.е. что в узлах

 

[x-yuri]

думаю, возможно и то и другое, тебя в каких случаях интересует, конкретнее
т.е. точно есть функции вычисляющие длину строки в символах и есть в байтах

 

[yana]

меня не время интересует, а количество операций для удаления и добавления в зависимости от количества элементов в дереве

готовых реализаций много и они показывают, что кол-во одинаково, а как должно все таки быть на самом деле?

 

[MiksIr]

x-yuri, я про индексы вообще-то

 

[x-yuri]

MiksIr думаю с символами, он же должен корректно сравнивать строки символов, а не байтов (речь ведь о VARCHAR etc) иначе было бы странно

 

[MiksIr]

А что, при сравнении строк символов есть разница - символы в однобайтовой кодировке или с плавающей длиной символа?

 

[x-yuri]

ты их либо посимвольно сравниваешь либо побайтово (определяется типом сравниваемых столбцов)
можно преобразовать столбцы в VARBINARY etc, тогда сравнение будет побайтовое

 

[MiksIr]

Еще раз задам вопрос - чем в сравнении строк вообще и VARCHAR-ов в частности будут отличаться результаты посимвольного сравнения и побайтового. И если ничем - зачем делать посимвольное сравнение вообще, если побайтовое проще в реализации и быстрее.
Судя по косвенной информации в узлах дерева все же байты... но, блин, может кто смотрел глубже...

 

[x-yuri]

при поиске в индексе происходит сравнение строк. Для каждой кодировки есть разные collation (определяют порядок символов в кодировке). Сравнение происходит в соответствии с этим порядком.
Для многобайтовых кодировок кроме порядка символов появляется еще один нюанс, вместо сравнения всех байтов символов сравниваются по очереди каждый байт

Судя по косвенной информации в узлах дерева все же байты... но, блин, может кто смотрел глубже...

)) все зависит от количества травы
а если серьезно, то в узлах дерева - строки, а рассматривать их как строки символов или как строки байтов зависит от того, кто их рассматривать будет . Mysql думаю их всегда как строки символов рассматривает