External Key Abbreviation in Software

Encoder Quick Response Code in Software External Key Abbreviation

Sec 4-2

In many European countries identi ers for individuals are constructed using similar techniques When such an abbreviated key is constructed at a later time, the sequence digit is not known, so that no unique transformation can be made In that case multiple records have to be retrieved and checked using further information, in a manner similar to the handling of collisions in a direct le organization A trade-o will have to be made between the length of the abbreviated key and the number of key collisions Abbreviation techniques are often essential within the le system Adequate fanout requires that we deal well with potentially long keys For character-string elds abbreviation by deletion of segments of low-order blanks is common Keys can be much more abbreviated, however, since keys should not need more bits than needed to discriminate among the n items in the le A theoretical minimum is a length of log2 n bits, and within one index block only log2 y bits should be needed for the key When processing data automatically, it is necessary that only one record be selected in response to a fetch request In the technique used externally a sequence digit was used to assure uniqueness A le system has to abbreviate the key so that any record, given a unique key, say the full name and address of a subscriber, can be uniquely identi ed by that key alone This will also avoid collisions Automatic abbreviation is feasible when the keys appear in a sorted sequence The portions of the key which do not discriminate between adjoining keys can then be deleted In order to bene t from internal abbreviation the index has to be able to handle variable-length keys The record marks which are needed to indicate key and record boundaries reduce the e ect of the abbreviation

Internal Key Abbreviation Variable-length keys Variable-length keys can occur naturally or be due to an abbreviation algorithm Naturally occurring variable-length keys, for instance, people s names, should in any case be allocated to variable-length elds, since a xed allocation of adequate space for the longest key may be prohibitive Key abbreviation is hence not costlier and is always desirable for variable-length keys Figure 4-6 shows a problem due to a xed-length abbreviation: in which volume would you nd a Canoe

Figure 4-7 illustrates opportunities for abbreviation of long keys The index shown uses the highest value of the key as the block anchor point The keys in our examples are numeric and letters indicate block addresses We will show how to delete redundant high-order and low-order segments of keys

Sec 4-2

If it is known from a higher level index that all index entries in a block refer to keys within a certain range, the high-order digits will be identical and this high-order segment can be deleted In Fig 4-7 the two leading digits of entries in block C of the second-level index were redundant, and were deleted from the individual entries In block D only one digit could be deleted, but in both cases the number of entries per block and the fanout ratio y has increased It is best to keep in a header of each index block the value of the high-order segment to allow reconstruction of the key from data within the index block Key abbreviations may be also applied to individual entries within blocks, as is shown in Example 4-2 for blocks B and D Now the entries are also variable within a block

High-Order Key Abbreviation Example 4-2

High-order key abbreviations D : 118+00=p,+10=q,11900=r,1 2+130=s,1220+1=t,+5=u,+9 =v,12+210=w,+384=x;

B : 000+13=a,+29=b,00+407=c, +704=d,0+2050=e,10+094=f ,+151=g;

The stored segments are separated by markers {+ = , ;} as indicated The highorder segment is repeated in front of a + symbol whenever the truncation changes Some analysis is needed to make the truncation optimal for the entire block If the key is of known length, the value and length of high-order segments omitted may be implied by the length of the remainder, as shown in Example 4-3

Example 4-3

High-order abbreviation for keys of known length D : 11800=p,10=q,900=r,2130= s,201=t,5=u,9=v,10=w,384 =x;

B : 00013=a,29=b,407=c,704=d ,2050=e,10094=f,151=g;

Similarly, the right-hand side of keys may frequently be shortened Indexes where the attribute is a potentially long string of characters, such as a name, sometimes arbitrarily limit elds to a xed number of characters When keys are poorly distributed, records may no longer have unique keys in the index This method can be seen in the volume headings of an encyclopedia as shown in Fig 4-6 Three characters here did not provide enough discrimination between Volumes 1 and 2, 2 and 3, 4 and 5, and 15 and 16 Instead of arbitrary limits, the contents of an index block can be inspected to determine how many low-order digits can be safely deleted In the earlier example (Fig 4-7), the two low-order digits of the rst index level (block A) can be deleted without loss of discrimination For insertion, omitted digits are taken to be nines The third character is required only because of the density of entries in the range between 13 000 and 14 000 The alternate version of block D of Fig 4-7 is shown in Example 4-4 with low-order abbreviation applied to the entries as well The dash (-) indicates the boundary for the low-order segment