tailieunhanh - Thuật toán Algorithms (Phần 25)

Tham khảo tài liệu 'thuật toán algorithms (phần 25)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | EXTERNAL SEARCHING 233 the record. Continuing a little further we can add S 10011 and E 00101 before another split is necessary to add This split also requires doubling the directory leaving the structure 000 000 000 01 A 01 A 001 001 01 E 001 01 E 001 01 E Disk 1 . 2021222230303030 010 01100 L Disk 2 A A EEE LN Oil Oil 10 N Disk 3 R ST X 100 10010 R 101 10011 S 110 10100 T 111 11000 X In general the structure built by ext endible hashing consists of a directory of 2d words one for each d-bit pattern and a set of leaf pages which contain all records with keys beginning with a specific bit pattern of less than or equal to d bits . A search entails using leading d bits of the key to index into the directory which contains to pages. Then the referenced leaf page is accessed and searched any strategy for the proper record. A leaf page can be pointed to by more one directory entry to be precise if a leaf page contains all the records uith keys that begin with a specific k bits those marked with a vertical line in the pages on the diagram above then it will have directory entries pointing to it. In the example above we have d 3 and page 0 of disk 3 contains all the records with keys that begin with a 1 bit so there are four directory entries pointing to it. The directory contains only to pages. These are likely to be smaller than keys or records so more directory entries will fit on each page. For our example we ll assume that we can fit twice as many directory entries as records per page though this ratio is likely to be much higher in practice. When the directory spans more than one page we keep a root node in memory which tells where the pages are using the same indexing scheme. For example if the directory spans two pages the root node might contain the two entries 10 11 that the directory for all the records with keys beginning with 0 are on page 0 of disk 1 and the directory for all keys beginning with 1 are on page 1 disk 1. For our example this split occurs when