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