Patent GB-1453695-A (GB)
Title: Data sorting system
IPC: G06F7/24
Filed: 1972-09-22
Abstract: 1453695 Sorting data HONEYWELL INFORMATION SYSTEMS Ltd 27 Dec 1973 [22 Sept 1972] 43880/72 Heading G4M Data having keys is written in blocks into a store 10 holding e.g. ten blocks. Indexes identifying the location of data in store 10 are held in a main list 13 in order of the keys of data in store 10. Using the indexes a best block, i.e. having the smallest difference between the largest and smallest keys is found and read out. Alternatively a quicker but less comprehensive search is used to find a nearly best block. A new block is written, the indexes are re-sorted and the process is repeated. When the best block is read out the part of the main list below the best block is moved up to fill the gap. For each item in the new block the position of its index in main list is determined. To save continually shifting the main list a pointer to the first empty location of the Buffer list 14 is inserted in the position of the index of the first key which is less than the new entry. The index of the new entry is inserted in the Buffer list into that location and the index of the first key below the new entry is inserted in the same position in the parallel list. If the next new entry occurs where a pointer exists the index in the Buffer list is replaced by a pointer to the next empty location in the Buffer list. A new index is inserted in this location and the index in the new pointer position is moved to a corresponding location in the parallel list. On reading the pointers overlap can be produced which must be corrected during the read out. When each best block is formed a link is produced which indicates the lowest key in the block, the disc address where the block is stored and how much padding occurs, i.e. whether the block is full of data or only partly full. The links are kept in link sequence in a link pool which can have sufficient capacity to contain all links but preferably has limited capacity. In the latter case as blocks are stored on discs their links are held in the link store until a certain capacity is filled. Blocks being stored then are accompanied with a link from the link pool having a key value just higher than the value of the stored block and the link removed from the pool is replaced by the link of the stored block so that one link can create access of a block and one or more further links. The pool is then filled with the lowest links of a sequence. A block may have more than one link attached. If the pool overflows a block of links may be removed and replaced by its own links. When all the best blocks have been formed the list area 10 is filled with blocks having the lowest keys, i.e. accessed from the lowest links in the pool. Each item of the block has an index in the main list arranged in key order and the items are read out to fill the output block 12. As each block is read out it is replaced by a new block. If there are not enough items in the item list 10 below the lowest key of the next block to be entered to fill output block 12 then either the item list is filled with the items of the next block having keys lower than the lowest key of the next following block or a block of the highest keys in the item list is stored in disc store and is provided with a new link and the next block is read in. If for each block written into the item list too few items are read out to output block 12 then a reversion to the best block procedure is performed. The blocks are written into the item list and best blocks are obtained, stored and links produced. Old and new link pools are produced for the earlier and the new links. Modification Chaining.-Each location in the item list has a key section, a data section and a chain section, the latter containing the item list address of the next item in key sequence, the chain sections being shifted to new items to relocate each item in sequence.