公开(公告)号：US3613086A

公开(公告)日：1971-10-12

申请号：US3613086D

申请日：1969-01-03

Applicant: IBM

Inventor： LOIZIDES EDWARD ,  LYON JOHN R

IPC: G06F12/00 ,  G06F17/30 ,  H03M7/30 ,  G06F7/22

CPC classification number: G06F17/30955 ,  H03M7/30 ,  Y10S707/99942

Abstract: Generating and searching a compressed key index (CK index) from a source index. The source index is a sorted sequence of uncompressed key''s (UK''s) in which a UK is a record key, as the term is ordinarily understood. The CK index comprises a plurality of compressed keys (CK''s). Each CK is a shortened representation of a UK. After its generation, the CK index can be searched for any search argument (SA). The format of a CK is generated by this invention to include a single control field (P), and at least one key (K) byte which is a byte taken from a UK. Each CK is generated from a pair of adjacent UK''s taken in their sorted sequence from the source index. The pair of UK''s are compared at corresponding byte positions from their highest-order bytes. The order of a byte position in a UK is determined by its significance in sorting the UK''s. The control field (P) in the CK format is generated to represent the highest-order unequal byte position in the pair of compared UK''s. Field (P) represents the lowest-order byte position in the CK. One key byte (K) is generated by copying a byte from the second UK in the pair at its byte location represented by the field (P). Additional key bytes are copied only when the current P (i.e. Pi) is greater than the prior generated P (i.e. Pi 1), in which case K bytes are copied from the UK byte positions (Pi 1+1) through (Pi). Also a pointer (i.e. address) is provided represented by the first UK in the pair from which the CK was generated. The CK index can be searched for any search argument (SA). The search uses one byte (A) at a time from the SA beginning with its highest-order byte. The setting of an equal-counter (EQU) indicates the position of the current byte A in the SA. While serially searching a CK index for the byte A, the control field (P) of each encountered CK is read. Then a factor value and the number of K bytes are derived for the current CK after determining if its Pi is greater than Pi 1. The factor value indicates the amount of high-order compression for the UK being represented. If Pi is greater than P 1, the prior control field (Pi 1) is the current factor value, and the current number of key bytes (K) is Pi less Pi 1. But if Pi is equal to or less than Pi 1, the current factor value is Pi, and only one K byte exists in the current CK. The current factor value is then compared to the current equal counter setting (EQU). If the factor value is greater than the search argument, the search continues by going to the next CK. But if they are equal, the highest-order K byte in the CK is compared with the current A byte. If A and K are equal, the next A byte and the next K byte (if any) are fetched, and they are compared. Whenever all K bytes in a CK compares equal with A bytes, or whenever any K byte is less than the A byte, the search passes to the next CK. Whenever any Pi is less than the current setting of the equal counter (EQU), or whenever any K byte compares high with the A byte, the search is completed after reading the pointer with the current CK, retrieving the pointer''s record, and comparing the SA to the UK in the record for verification that the correct record has been obtained. The search is then ended in an index having an ascending sequence.