Hashing is the internal function that performs a mathematical computation, which yields an address indicating where the record resides. D3 defines the concept of groups as dividing the linear space for data into equally sized blocks. The number of groups in a file should always be a prime number to facilitate efficient hashing. An item hashes to a specific group. To add the item, it is appended to the series of items already residing within that group. When the group (frame) becomes full, additional blocks of space are linked to that frame as needed. D3 Hashing Algorithm is very efficient:
|
x = 0 for j=1 to len( item-ID ) x = ( x*10 ) + seq( item-ID[ j,1 ] ) next j group = rem( x, modulo ) frame.id = group + base.fid |
where
item-ID is the key to accessing the item
group is the relative frame where the item hashes
modulo is the number of groups (frames) in the data file primary file space
frame.id is the final address where the item hashes
base.fid is the starting frame address of the data file
D3 converts ASCII into a numeric value, divides it by the number of available groups, and takes the remainder. That remainder is the relative group number to which the item resides (hashes).
Adding an Item
The system hashes to the group and scans the group for an empty spot to write the item. If it finds the item already there, it reports a duplicate item. If it finds an empty spot, it puts the item in. If it reaches the end of the group, or if there is not enough remaining space in the group to add this item, the item overflows the capacity of the group. D3 must make the group bigger. It grabs a spare frame and links it to the group using a linked-list method. Then it adds the item using the new group space. Items are always added at the end of the group, or at the end of the chain of overflow frames. Each group, therefore, is a potential linked-list chain of frames.
Deleting an Item
The system hashes to the group and scans through the group and successive overflow frames until it finds the item. If the item does not exist, the system reports the item not found. If found, the item is deleted and all following items in the group are shifted to eliminate the gap. If an overflow frame becomes empty from repositioning, it is unlinked and returned to overflow.
D3 actually does not delete items right away. Items are initially marked as deleted, then actually deleted during the file backup process when the system is sure an undelete is not wanted.
See Also