Hi Flex0!

Не совсем "половинным делением". От одной страницы индексного тега может
идти >2 ссылок на "нижележащие" страницы. В идеале, до 55 страниц (в
компактном индексе для "промежуточных" страниц формат отводит 500 байт на
информацию о самом ключе + адрес страницы + ещё 4 байта для не очень ясного
"intra-index pointer") - это если размер ключа - 1 байт (логическое поле без
NULL например, или CHAR(1) поле). Таким образом даже для вырожденного
случая - таблицы с 1Млрд записей (каждая размером 2 байта - 1 из которых
Delete Mark) в идеале потребуется всего 5 считываний индексных страниц (на
уровне страницы "листа" формат позволяет хранить от 120 до 240, но обычно
160 записей - в зависимости от "разброса" номеров строк (т.е. будет отведено
на Recno+BitCount 2, 3 или все 4 байта в "упакованном" формате - разбросом
самих "ключевых значений" в данном случае можно пренебречь, считая что на
них уходит 1 или 2 байта)). Кстати говоря это чисто теоретический пример -
т.к. такой индекс создать не получится - он по размеру будет превосходить
2Гб чего фокс не допускает. Впрочем для максимального же 2Гб cdx все эти
рассуждения также справедливы - в общем всё зависит от длины ключевого
выражения...

P.S. Естественно что огромную роль тут играет "сбалансированность" дерева и
степень заполненности оконечных индексных "листов" - тут кстати есть большие
различия, обусловленные использованием той или иной версии фокса. Известно
что VFP7 создаёт наиболее "разряжённые" индексы (они больше по объёму -
вплоть до 1.5 раз по сравнению с другими версиями фокса) - зато они более
эффективны при большом числе операций вставки (и возможно замены)...

P.P.S. для всех желающих понаблюдать за внутренней работой фокса с dbf можно
рекомендовать утилиту FileMon от небезызвестного Марка Руссиновича (сайт
раньше был sysinternals.com)

Posted via ActualForum NNTP Server 1.2

Hi Flex0!

Если кое-кто не в состоянии понять что данный алгоритм ЭФФЕКТИВНЕЕ простого
бинарного дерева (как по скорости поиска, так и по эффективности
использования дискового пространства, по минимизации операций доступа к
физическому носителю), то мне искренне жаль этого человека... Тем более что
он (алгоритм) даже и не называется нигде B-tree... Просто похож на каком-то
уровне абстракции. Я кажется встречал термин B+ tree или что-то в этом духе,
но точно не помню. Одно 100% - это НЕ бинарное дерево в чистом виде.

Насчёт страницы в 4К даже не знаю что и сказать - приведенные цитаты с одной
стороны справедливы - да именно так устроена память в IA32 процессорах (хотя
это лишь один из уровней абстракции - сегментная адресация уже будет
несколько сложнее простой страничной... Хотя в Windows не используются ВСЕ
возможности процессоров данной архитектуры). С другой стороны НИЧЕГО
БЛИЗКОГО к тому как ЧИТАЕТСЯ ФАЙЛ, в частности индексный в память, и как он
затем используется фоксом нет. Заметь, что я не говорю о всяких косвенно
влияющих факторах, типа секторов и кластеров имеющихся на большинстве типов
накопителей, про размеры сетевых пакетов (при сетевом размещении файлов) и
т.п.

Порой одного знания голой теории недостаточно - надо ещё и думать, и
экспериментировать. Повторюсь - любой желающий ознакомится с тем как именно
фокс работает с файлами (абстрагируясь от тонкостей реализации драйверов как
жёстких дисков, CD и прочих, так и файловой системы), может это сделать
скачав и запустив утилиту FileMon.

Posted via ActualForum NNTP Server 1.2

Hi Flex0!

1) ВНИМАТЕЛЬНО ЧИТАЙ ИЗНАЧАЛЬНЫЙ ВОПРОС!!!! то что за привычка - мы тут про
Фому, а ты про Ерёму.
2) Процессу в Win32 системах выделяется всего 2Гига памяти (3Гига под
некоторыми серверными версиями ОС) - остальные 2 Гига (или соответственно 1)
резервируются для самой системы, и собственно пользовательскому коду
недоступны (для фокса код рантайма это ТОЖЕ пользовательский код фокс вообще
написан на C++ и НИЧЕМ не отличается от других приложений на нём
написанных).
3) Фокс запрашивает себе память штатными механизмами - если ты внимательно
почитаешь про Heap, а заодно про File IO (хотя-бы банальнейший ReadFile) то
перестенешь говорить явные глупости - страничная организация памяти НЕ
МЕШАЕТ приложению запрашивать себе блоки размером скажем в 1 байт. Если
довести твои рассуждения до абсурда, и вспомнить что физически ОЗУ компа
представляет собой от 4 до пары десятков микросхем, то твои высказывания
аналогичны тому, что раз приложение запросило себе 1 байт памяти, то оно
отхватило себе целиком всю микросхему, и следующий запрос захватит следующую
микросхему :) Поверь мне, что если приложение запросит себе 100 блоков по 1
байту, то оно скорее всего получит все эти "кусочки" в рамках одной и той-же
страницы, даже учитывая накладные расходы на хранение управляющих структур.
> Можно петь любые дифирамбы про тот как фокс работает с файлами, что он там
> открывает и по сколько. На уровне ОС это происходит именно так как я
> описал.
ЧТО происходит? Чтение файла с носителя??? Т.е. если у меня имеется 10000
файлов по 1 байту, то по твоей логике для их считывания мне
потребуется 40 Мегабайт памяти??? Или если у меня имеется один файл размером
2Гига, то я не могу его обработать по частям, не считывая ЦЕЛИКОМ в память -
т.е. не выделяя себе как минимум 2Гига памяти??? Странно, но вот прямо
сейчас я могу работать ОДНОВРЕМЕННО с несколькими dbf-ами, суммарный размер
которых (вместе с cdx) превышает 2Гига, на ОС которая выделяет <2Гиг памяти
на процесс (учитывая что в эту-же память грузятся и все системные dll-ки,
фоксовый рантайм...) Парадокс?
Только не надо начинать тут рассказывать про Memory-Mapped files - для
dbf/cdx/fpt фокс не использует эту технологию, он совершенно трививально
считывает необходимые кусочки файла в локальные блоки памяти - размер
которых НЕ кратен размеру страницы памяти ОС - да и с чего-бы это ему было
необходимо. Ты можно подумать при написани C# программ тоже выравниваешь все
структуры по границе 4Кб :) Особенно учитывая что в C# в принципе невозможно
это сделать, т.к. там работа НЕ ведётся через указатели, и физическая
организация памяти скрыта от программиста.
В общем предлагаю заканчивать валять ваньку, и признать что не про то ты
поешь, как минимум не тот вопрос прочитал.

Posted via ActualForum NNTP Server 1.2