B + Tree CPU время поиска

Question

Мне было просто интересно, как бы вы рассчитали время наихудшего случая для некластеризованного и кластеризованного дерева b +?

Например, скажем, у меня было 1 000 000 записей (1 строка = 100 байт), страницы диска - 4000 байт, ключ - 20 байт, а время доступа к странице - 40 мс. Как бы я рассчитал с использованием этих переменных некластеризованное и кластеризованное время худшего случая с b + деревом?

Я знаю, что для вычисления высоты / уровня дерева b + вы используете следующее (я думаю):

logF(keys)

где F = количество ветвей.

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

Любая помощь приветствуется!

Answer 1

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

logF (ключи) + N - это N число переходов в узле индекса.

, поэтому в итоге это будет

H = высота дерева, которая будет равна 3 или 4.

H + N = 4 + (4000/20) = 204 операций ввода-вывода

, скажем, они находятся в памяти и хотят видеть время процессора, тогда это будет

CPU= 204 * 0,04 = 8,16 с.Хотя 40 мс для перемещения страницы в памяти это довольно много времени, я думаю (для чтения с диска может иметь смысл), но я думаю, что вычисления в порядке.