Algorithms performance in function of disk accesses
$L := Number \ of \ index \ levels$
$K := Number \ of \ overflow \ pages \ chained \ with \ a \ data \ page$
| Member Function |
Performance |
Non Primary Key |
Primary Key |
locate(KeyType key) |
$\mathcal{O}(L)$ |
Makes 1 access for each index level |
Makes 1 access for each index level |
search(KeyType key) |
$\mathcal{O}(L+K)$ |
Locates the key and then searches in all the chained pages |
Locates the key and iterates over each chained data pages until the first record such that key = index(record) is found |
insert(RecordType& record) |
$\mathcal{O}(L+K)$ |
Locates the key and then looks for the first non-full data page |
Locates the key and verifies in all chained pages if the key already exists and inserts the record at the first non-full data page found |
- When there is no space for a new record in a chain of record pages, a new overflow page is created and linked to previous overflow pages.
- ISAM tree is static; therefore, the number of disk accesses used to locate a key (known as $L$) is constant, as it never changes.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent