33. Організація роботи з таблицями з використанням двійкового пошуку.

Для вибірки відповідного запису з таблиці через індекс у формі списку треба виконати послідовність порівнянь у відповідності з визначеними відношеннями рівності та порядку.

// вибірка за лінійним пошуком через індекс в формі // списку

struct recrd*selLin(struct keyStr kArg,

struct indStr *ndx)

{while(ndx!=NULL&&cmpKey(ndx->pKyStr,kArg))

ndx=ndx->pRtPtr;

if(ndx==NULL)return NULL;

return ndx->pKyStr;

}

Якщо лінійний пошук треба виконати через деревоподібний індекс, то для цього використовуються методи повного рекурсивного обходу дерева. Методи двійкового пошуку можна використовувати лише у впорядкованих деревах або у відповідних індексах. Тобто індекси для виконання такого пошуку повинні бути попередньо впорядковані і для роботи з ними треба мати функції включення відповідно порядку та балансування дерев.

//вибірка за двійковим пошуком через індекс в формі дерева

struct recrd*selBin

(struct keyStr kArg,// ключ аргументу пошуку

struct indStr *ndx)// адреса кореня індексу

{ while(ndx!=NULL&&(i=cmpKey(ndx->pKyStr,kArg)))

{if(i>0)ndx=ndx->pLtPtr;else ndx=ndx->pRtPtr;

}

if(ndx==NULL)return NULL;

return ndx->pKyStr;

}

// виведення індексованого рядка базової таблиці

void prRow(struct recrd* rw)

void prRow(struct recrd* rw)

{if(rw==0)printf("is absent\n");

else printf("%10s %3u %5.3f\n",

rw->key.str,rw->key.nMod,rw->func._f);

}

Системні програми в процесі свого виконання використовують власну вбудовану інформаційну базу (IБ), а також будує інформаційну базу про текст на заданій мові.

39. Відношення порядку на ключових полях.

Відношення порядку

Впорядкування таблиць за ключовими полями стає можливим лише у випадку впорядкування кодів кожного з потрібних ключових полів. Відношення порядку встановлюються для даних з однови-мірними множинами визначення значень (доменами). Всі числові і перенумеровані типи даних, в тому числі і полів, мають визначені відношення порядку. Тому набори операцій мови С/C++ "=" та "!=", які створюються за умовчанням, необхідно розширити додатковими операціями відношень мови С "<", "<=", ">=" та ">", в тому числі з урахуванням полів з вказівниками.

Для визначення відношення порядку багатокомпонентних типів необхідно, щоб кожний компонент мав відношення порядку, і щоб узагальнююче відношення будувалося за допомогою моно-тонних функцій. Відношення порядку завжди визначаються при побудові індексів в реляційних системах управління базами даних (СУБД), наприклад, в більшості SQL-серверів як зважене об’єд-нання полів, а в деяких системах, наприклад у FoxPro, припустимий індексний вираз, що визначає функцію полів.

Методи двійкового пошуку можна використовувати лише у впорядкованих таблицях або у відповідних індексах. Тобто таблиці для виконання такого пошуку повинні бути попередньо відсорто-вані і для роботи з ними треба створити функцію сортування.