как сделать из слона муху

ФЛЕНОВ МИХАИЛ AKA HORRIFIC

Спецвыпуск: Хакер, номер #071, стр. 071-048-5

2 НА ПОИСК ЛЮБЫХ ДАННЫХ ЗАТРАЧИВАЕТСЯ ПРИМЕРНО ОДИНАКОВОЕ ВРЕМЯ.

3 ДЛЯ ЭФФЕКТИВНОЙ РАБОТЫ ВПОЛНЕ ДОСТАТОЧНО СТОЛЬКО ПАМЯТИ, СКОЛЬКО ЗАНИМАЕТ ОДИН ИНДЕКСНЫЙ БЛОК. ВСЕ БЛОКИ ДЕРЖАТЬ В ОПЕРАТИВКЕ НЕТ СМЫСЛА, НО ЕСЛИ ЕСТЬ ЛИШНЯЯ ПАМЯТЬ, ТО МОЖНО КЭШИРОВАТЬ БЛОКИ.

Недостаток один, но очень серьезный – поддерживать такой индекс не так уж и просто.

Вот так при минимуме затрат можно быстро искать и обрабатывать большие объемы информации. В данном случае мы затронули разновидность лиственных под называнием B-Tree (Balanced Tree или сбалансированные деревья). Бывают и другие разновидности, но это уже совершенно другая история.

[кластер или нет.]

Существует две разновидности деревьев – кластерные и некластерные. В первом случае на кончиках веток индексного дерева находятся сами данные. Это значит, что, прогулявшись по всем блокам, мы находим непосредственно искомые данные. Получается, что в данном случае данные упорядочены с помощью такого индекса физически. Конечно же, на один список (таблицу) можно создать только один кластерный индекс, потому что упорядочить физически по двум разным параметрам один и тот же набор данных просто нереально.

В некластерном дереве на кончиках веток находятся только ссылки на данные, а сами данные могут находиться где угодно на диске и в любом порядке. Таких индексов можно создавать сколько угодно.

[итого.]

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

Пример динамического массива

type

PMassivItem = ^TMassivItem;

TMassivItem = record

nextItem:PMassivItem; //следующий элемент массива

prevItem:PMassivItem; //предыдущий элемент массива

Name:String; // пример данных, которые нужно хранить

// еще здесь могут быть поля элемента массива

end;

TMassiv = class

public

FirstItem:PMassivItem; // первый элемент списка

LastItem:PMassivItem; // последний элемент списка

itemsNumber:Integer; // количество элементов

constructor Create(str:String); // конструктор

procedure AddItem(str:String); // добавление элемента

procedure DeleteItem(index:Integer); // удаление

end;

procedure TMassiv.AddItem(str:String);

var

newItem:PMassivItem;

begin

newItem:= new(PMassivItem);

newItem.Name:=str;

newItem.nextItem:=nil;

newItem.prevItem:=LastItem;

LastItem.nextItem:=newItem;

LastItem:=newItem;

Inc(itemsNumber);

end;

constructor TMassiv.Create(str:String);

begin

itemsNumber:=1;

FirstItem:=new(PMassivItem);

FirstItem.Name:=str;

FirstItem.nextItem:=nil;

FirstItem.prevItem:=nil;

LastItem:=FirstItem;

end;

procedure TMassiv.DeleteItem(index: Integer);

var

i:Integer;

currentItem:PMassivItem;

begin

// поиск удаляемого элемента

currentItem:=FirstItem;

for i:=0 to index-1 do

currentItem:=currentItem.nextItem;

// наводим новые связи и освобождаем память

if currentItem.prevItem<>nil then