Смирнов Сергей. Создание эффективной реализации сортированного списка с использованием generics

B+-деревья
Реализация двухуровневого массиваСтатья содержит описание реализации линейного односвязного списка на базе массивов. Пример реализации приведен с использованием Visual Basic 6.0Так случилось, что я стал программистом 1С. Все прекрасно в этой среде, за исключением скорости. Эту проблему можно решить только одним способом: прямым доступом к файлам и обработкой результатов на компилируемом языке в памяти.
Так, для группирования данных нужны алгоритмы поиска и вставки. И мое сознание, отягощенное бухгалтерским учетом, не нашло ничего лучшего, чем использовать аналог TList (SortedList), представляющий собой динамический массив со свойствами «емкость» и «количество элементов».
Упорядоченность в этом массиве поддерживается с помощью компараторов, а при поиске используется алгоритм половинного деления с поиском нужной позиции i по ключу с условием (Items [i]=Key) AND (Items[i-1] Key). Если такого ключа нет, то все данные с позиции i переносятся на одну позицию в большую сторону. При этом используются процессорные команды MOVSW и MOVSB, которые выполняются очень быстро. При полном заполнении массива его размер увеличивается либо за счет свободных адресов, следующих за конечным адресом в массиве, либо с помощью выделения нового массива большей емкости с копированием данных из оригинала.
Но время шло, и объем группировок вышел за 10000 записей. Мой AMD K6 200 (мощный по тем временам компьютер) начал работать слишком меленно. И не удивительно – количество сдвигаемых элементов в среднем стало равно N2/4, то есть 108.