Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[124]

tent data structures) позволяют получать информацию о предыдущих состояниях (версиях содержимого) структуры, а иногда и менять предыдущие версии. Общую методику сохранения предыдущих версий списочной структуры данных (с небольшими потерями по времени и памяти) предложили Дрисколл, Сарнак, Слеатор и Тарьян [59]. Напомним, что в задаче 14-1 подобная структура строилась для динамического множества.


Б-деревья

В этой главе мы рассмотрим один из видов сбалансированных деревьев, при котором обеспечивается эффективное хранение информации на магнитных дисках и других устройствах с прямым доступом - Б-деревья.

Б-деревья похожи на красно-черные деревья; разница в том, что в Б-дереве вершина может иметь много детей, на практике до тысячи (в зависимости от характеристик используемого диска). Благодаря этому константа в оценке О (log га) для высоты дерева существенно меньше, чем для черно-красных деревьев.

Как и черно-красные деревья, Б-деревья позволяют реализовать многие операции с множествами размера га за время О (log га).

Пример Б-дерева показан на рис. 19.1. Вершина ж, хранящая га[ж] элементов, имеет га[ж] + 1 детей. Хранящиеся в ж ключи служат границами, разделяющими всех её потомков на га[ж] + 1 групп; за каждую группу отвечает один из детей ж. При поиске в Б-дереве мы сравниваем искомый ключ с га[ж] ключами, хранящимися в ж, и по результатам сравнения выбираем один из га[ж] + 1 путей.

Точное определение Б-дерева и логарифмическая (от числа вершин) оценка его высоты приводятся в разделе 19.1. В разделе 19.2 описаны операции поиска и добавления элемента в дерево; удаление обсуждается в 19.3. Но прежде надо объяснить, в чем отличие магнитных дисков от оперативной памяти, делающее выгодным использование Б-деревьев.

Рис. 19.1 Б-дерево с английскими согласными в качестве ключей. Внутренняя вершина х с п[х] ключами имеет п[х] + 1 детей. Все листья имеют одну и ту же глубину. Светлые вершины просмотрены в процессе поиска буквы R.


Рис. 19.2 Дисковод Структуры данных на диске

Компьютер использует разные виды памяти. Оперативная память (main memory) представляет собой микросхемы, каждая из которых вмещает миллионы битов. Цена такой памяти (в расчёте на бит) выше, чем для вторичной памяти (secondary storage). Типичный компьютер использует в качестве вторичной памяти жёсткий диск, объём которого может на несколько порядков превосходить объём оперативной памяти.

Магнитная головка (см. рис. 19.2) записывает и читает данные на магнитном слое вращающегося диска. Рычаг может переместить её вдоль радиуса диска. После этого головка читает/пишет данные на одной из дорожек (tracks) диска. Обычно каждая дорожка делится на определённое число равных по размеру секторов (каждый может занимать несколько килобайтов). Обычно записывают или считывают сектор целиком. Время доступа (access time), которое требуется чтобы подвести головку к нужному месту диска, может быть достаточно большим (до 20 миллисекунд); в оперативной памяти такой задержки нет, потому что нет механического перемещения. Как только головка диска уже установлена, запись или чтение диска происходит довольно быстро. Часто получается, что обработка прочитанного занимает меньше времени, чем поиск нужного сектора. Поэтому, оценивая качество алгоритма мы будем учитывать два параметра:

•число обращений к диску, и

•время вычислений (время работы процессора).

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

Алгоритмы, работающие с Б-деревьями, хранят в оперативной



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]