公开(公告)号：US3643226A

公开(公告)日：1972-02-15

申请号：US3643226D

申请日：1969-06-26

Applicant: IBM

Inventor： LOIZIDES EDWARD ,  LUCAS DONALD J ,  STEIGERWALT GEORGE F

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

CPC classification number: G06F17/30949 ,  Y10S707/99933

Abstract: A method and means for searching a compressed index generated by the method and means disclosed in U.S. Pat. application Ser. No. 836,930 filed the same day as this application. Two types of searches are disclosed, (1) a multilevel search, and (2) a onelevel search. The multilevel search begins at the highest, or apex level of a multilevel compressed index and searches one block at each level. The multilevel search ends after finding a pointer at the lowest level in the index. The pointer found at the lowest level addresses a data block containing the information searched for. The one-level search can enter the multilevel index at any level and serial search plural blocks for the correct pointer to a block at the next lower level.

Abstract translation: 一种用于搜索由美国专利公开公开的方法和装置产生的压缩索引的方法和装置。 应用程序 在本申请的同一天提交的第836,930号。 公开了两种类型的搜索，（1）多级搜索，以及（2）一级搜索。 多级搜索从多级压缩索引的最高或最高级开始，并在每个级别搜索一个块。 在索引中找到最低级别的指针后，多级搜索结束。 在最底层找到的指针寻址包含搜索信息的数据块。 一级搜索可以进入任何级别的多级索引，并串行搜索多个块，以便正确指向下一级别的块。

公开(公告)号：US3603937A

公开(公告)日：1971-09-07

申请号：US3603937D

申请日：1969-06-26

Applicant: IBM

Inventor： LOIZIDES EDWARD ,  STEIGERWALT GEORGE F

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

CPC classification number: G06F17/30949 ,  Y10S707/99942

Abstract: A method and means for generating a multilevel compressed index. The high-level blocks of the index have an entry format of CK1, CK2, R in which R is a pointer to a next lower level compressed index block, and CK1, and CK2 are each compressed keys generated from uncompressed keys (UK''s) represented by pointers on opposite sides of the end boundaries of select low-level compressed index blocks. The generated multilevel index can be searched using the invention described in U.S. application No. 836,825.

公开(公告)号：CA944083A

公开(公告)日：1974-03-19

申请号：CA83263

申请日：1970-05-21

Applicant: IBM

Inventor： LOIZIDES EDWARD ,  LUCAS DONALD J ,  STEIGERWALT GEORGE F

IPC: G06F12/00 ,  G06F17/30

公开(公告)号：CA944082A

公开(公告)日：1974-03-19

申请号：CA83261

申请日：1970-05-21

Applicant: IBM

Inventor： LOIZIDES EDWARD ,  STEIGERWALT GEORGE F

IPC: G06F12/00 ,  G06F17/30

Abstract: 1280486 Information retrieval INTERNATIONAL BUSINESS MACHINES CORP 3 June 1970 [26 June 1969] 26724/70 Heading G4C Means for generating a multi-level compressed index comprises means for assembling a plurality of boundary pairs of uncompressed keys, means for assigning a respective pointer to each of the uncompressed key pairs, the pointer representing the location of a compressed index block represented by the uncompressed key pair, and means for compressing uncompressed keys. A sorted index of uncompressed keys, each accompanied by a pointer to associated data, is read from an I/O unit a block of keys at a time (with their pointers) into a low store, the last key of each block and the first key of the next (without their pointers) being also placed in a high store where a pointer (selected sequentially from a pointer table) is appended to each such pair of keys. Each block of keys in the low store is compressed as in Specification 1,280,484 (referred to) and passed to an I/O unit to make room for the next block of uncompressed keys, the compressed block forming part of a first level of a compressed index. When a block of uncompressed keys has accumulated in the high store, it is passed to an I/O unit as a block of an uncompressed second level of the index. When the original sorted index has been completely processed in this way, the uncompressed second level of the index is read into the low store a block at a time, with the last two uncompressed keys of each block being also placed in the high store. Appending of pointers, compression, &c. take place as with the previous level, to give a compressed second level and an uncompressed third level. The latter is then used like the uncompressed second level, and so on, until the last generated compressed level has a predetermined number of blocks (normally one) or alternatively until a predetermined number of levels has been generated if this point is reached first. Each pointer in any level above the first, points to a corresponding block in the next lower level. A pointer to the single block of the highest level may be appended to a stored name of the index. Searching in the generated index requires only one block per level to be searched, and usually only a part of that since the search in a given compressed block ends whenever the search argument is lower than a compressed key with which it is compared. Magnetic tape, disc or drum are mentioned for the I/O units.