Ущільнення сигналу і виділення ущільненого сигналу | Комп'ютерні мережі | топологія мереж | Методи передачі даних в мережах | Організація обміну інформацією в мережі | Обробка інформації | Операції над даними | лінійні списки | Способи доступу по первинному ключу | блоковий спосіб |

загрузка...
загрузка...
На головну

Індексного-послідовний спосіб

  1. B. позапарламентських спосіб порядок перегляду Конституції РФ
  2. II-2.5.3. Способи завдання цільової функції
  3. III. Здатність до розмноження
  4. IV етап. Спосіб представлення інформації.
  5. IV. Здатність до диференціювання (спеціалізації) клітин
  6. V. Способи упаковки шприців, голок, інструментів для стерилізації

Лінійний список впорядковується за первинним ключем. Аналогічно блочному методу доступу, він ділиться на віртуальні блоки розміром vN. Потім ключові поля останніх елементів блоків разом з порядковими номерами цих елементів в списку включаються в додаткові списки, які називаються індексами. Таким чином, для списку з таблиці 5 (далі - основного списку):

Таблиця 5

 № п / п  Прізвище  ім'я  По батькові  Номер залікової книжки  Домашня адреса
 Скворцов  Олег  Іванович  пр. Миру, 45 - 3
 Соколов  Юрій  Кузьмич  вул. Леонова, 23 - 98
 Строков  Іван  Іванович  вул. Червона, 9 - 2
 Супруненко  Віктор  Єгорович  Каштанова алея, 23 - 5

буде побудований індекс, представлений в таблиці 6:

Таблиця 6

 № п / п  Прізвище  № п / п в основному списку
 Соколов
 Супруненко

поле № п / п в основному спискує полем з посиланнями на деякі елементи іншого списку. Надалі подібні поля будемо називати посиланням. З їх допомогою підтримується зв'язок елементів одних таблиць з елементами інших таблиць, а також зв'язок між елементами однієї і тієї ж таблиці, яка утворює ланцюжка (ланцюга) елементів.

При поіскепо ключу Додоступ спочатку за індексом визначається блок, в якому може знаходитися шуканий елемент. Потім виконується звернення до цього блоку в основному списку і, як правило, методом послідовного сканування, проглядаються елементи блоку. Принципова відмінність цього методу від блокового полягає в тому, що при невеликому розмірі індексу він може бути розміщений цілком в основний пам'яті комп'ютера на час виявлення необхідного блоку. Оскільки розмір основного списку в загальному випадку досить великий, така оперативна його обробка або неможлива, або скрутна. Слід зазначити, що індекс є в свою чергу лінійним списком, за яким може бути організований будь-який спосіб доступу з розглянутих раніше.

Приклад 7.Нехай в основному списку таблиці 5 треба переглянути адресу студента на прізвище Скворцов, тобто qперегляд = (Прізвище= Скворцов, Домашня адреса), Де Кдоступ = Скворцов. Завдання виконується в такий спосіб:

1. вибирається перший елемент в індексі;

2. його ключове поле порівнюється з шуканим: Соколов = Скворцов;

3. оскільки умова не виконується, перевіряється, чи можливо знаходження шуканого елемента в поточному, першому, блоці. Для цього перевіряється умова: Соколов> Скворцов;

4. умова виконується, тому з сусіднього поля індексу вибирається посилання на останній елемент першого блоку в основному списку - це 2;

5. за цим номером виконується звернення до попереднього, тобто першого, елементу основного списку;

6. ключове поле цього елемента порівнюється з шуканим ключем: Скворцов = Скворцов;

7. оскільки ключові поля рівні, виводиться адреса: пр. Миру, 45 - 3; алгоритм закінчує роботу.

Додаваннянового елемента виконується способом, аналогічним розглянутим раніше, за винятком того, що модифікується також і індекс. А оскільки індекс є також упорядкований по ключу лінійний список, то і до його поповненню придатні способи поповнення лінійних списків.



двійковий спосіб | Індексного-довільний спосіб
загрузка...
© um.co.ua - учбові матеріали та реферати