US 4,633,391 AGrant
Extended Index for Digital Information Storage and Retrieval Device
Issue Date:1986-12-30
•6 Claims
•10 Drawing Sheets
Abstract
In extended for a digital information storage device comprised of a host having the capability of placing Key identifiers in the header of user data blocks to be recorded, a recording device having a random access memory said memory having an Index register, a plurality of Pointer Table registers, a Target register, a Key Start register, a Key Length register and a Pointer Table Select register, and a micro-processor able to perform an indirect binary search between a selected Pointer Table the contents of the Pointer Table being the address from the Index (the address being the band location, and the register contents of the Index being the Identifier Keys selected by the host, said Keys being the lowest Key entry on any given band).
Metadata
Assignee
- Storage Technology Partners II
Inventor
- John P. Rundell
Application Information
Application Number:US 5443296
Filing Date:1983-10-21
Priority Date:1983-10-21
Art Unit:232
Classifications
IPC:
G06F 1540
Field of Search:
364200 MS File;900 MS File
Patent Drawings (10 sheets)
Description
Background of the Invention
This invention relates to the field of retrieval of information stored on digital information storage disks, and in particular to an apparatus and method for rapidly and efficiently locating user data stored on an information recording disk.
With information storage devices such as magnetic tape drives, the need for extensive indexing is minimal since the data is recorded, and must be read, sequentially. However, with the development of random access information storage disks, the need for indexing methods developed, in order to find specific blocks of user information. Also, as digital data has been ever more densely written on information recording disks, the need to provide a means for rapidly and efficiently searching and recovering specific user data has become even more difficult.
The early response to the problem was in the indexing of disk data. That is, providing a short hand means, which has been generally entitled a Key, whereby user data is given a designation which uniquely identifies the larger data grouping, thereby allowing a somewhat more efficient search of the index in order to find the specific data grouping sought. Indexing has generally involved either placing some unique identifier Key in the header portion of the user data and storing that identifier in a separate memory, or by taking some unique characteristic of the user data and making that value the Key. In magnetic disks, as the data is recorded and transferred to the host, an extensive Index, indicating the platter content and location of specific data blocks, is created for that disk. This was a partial solution to the problem of data storage and efficient retrieval. An early example of this method is the IBM Count Key system.
However, as data is written more densely on the disk surface, and since indexing has taken up ever more real estate on the platter surface the need for even more efficient disk indexing systems has become evident. Users have a continuing need to rapidly access the stored data. The more extensive the Index, the longer the search time necessary to find a specific set of user data. With the data being more densely written on the disk surface, this time has increased, with a corresponding decrease in the utility of the system.
Also, the need has developed for a user to be able to search a given data base for a specific set of data based upon more than one Key indexing method. To do this, a multiple Key system is necessary, in that if the data sought could be more efficiently searched based upon a "sort" other than the means by which it is initially indexed, the search would be less inefficient and time consuming. For example, if the data were sorted and indexed with regard to social security numbers, a search that could be efficiently done by address or by age would be most difficult. The present systems in use generally have a single identifier Key and sort for the indexing method.
In more recent years, there has also been increased development in recording devices having removeable media. This has intensified the need for an efficient means of indexing data recorded on the device surface, because to efficiently access the data recorded on the disk, the disk must carry its complete Index with it, and as storage devices move toward using single platters as opposed to disk packs, the need for an efficient indexing system has become critical.
Most importantly, as optical media having its write once only capability has been developed, the prior indexing and searching schemes have become inappropriate. In magnetic disk, with its erasable capability, data can be replaced and/or rather easily re-ordered. In particular, if data has a specific sequence and new data is presented which should be inserted therein, it is relatively easy to re-record the data placing the new entry in its appropriate place. Also, if a defect in the platter surface prevents the recording of data, the data can be recorded elsewhere and a pointer recorded leading to the new location, thus allowing the host to view the data as recorded on the platter location intended. These approaches are not possible with noneraseable media. Therefore, a new method of writing data, indexing and searching such data must be developed. What is needed therefore, for all information recording disks, is a more efficient means for indexing and searching for user data that does not also use up significant platter storage capacity. Also needed is a tool which would allow the user to efficiently access ever larger volumes of data on the platter surface based upon multiple sorting and indexing schemes, without a corresponding increase in the use of platter storage capacity for such indexing. Also needed is a system which would allow a "write once only" disk to be written upon, indexed, and searched, at least as efficiently as erasable media. And finally, a system is needed which can support an Index for a device having removeable media.
Brief Summary of the Invention
In the preferred embodiment, the disk is formatted into concentric blocks each block having between therein a plurality of user tracks, each trach having thereon a plurality of user blocks. In the host, when data is to be recorded, it is ordinarily built up into user blocks. Before recording, in the host the user identifies a Key or a set of Key values which will be used to Index the data. The protocol for the device requires that for a given band, no user block of information be recorded if the Key value for that block is smaller than any Key value previously recorded with that band. This is necessary for the efficient operation of the indexing and searching functions.
Once the data is recorded on the disk band, the device compares the Key value for that block with the Key value written on the Index band identifying the lowest Key value for that block and only recording that value if it is a lower value. Therefore, the latest entry in the Index band will always indicate the lowest Key value recorded on any given band. Once an entry is written on the Index band, it is also entered into the Index register located in the random access memory in the device. This Index is set up with the address being the physical number of the band on the disk surface with the Index register contents being the lowest Key value on that band.
The random access memory also has located therein a separate pointer table register for each user Key designated by the device user. These pointer table Keys are sorted with the contents being the address from the Index band in the sequence as determined by the specific user Key designated in the Index. For example, if the first user Key is based upon the first five entries in the Index register, the first pointer table will be sorted in that sequence whereas if the second user Key is based upon the last two entries in the Index register, pointer table 2 will be sorted in that order.
In order to perform a search, the user identifies a Target Key, the Key in the header of the specific block sought. This value is stored in a Target Key register, along with information stored in a start Key. Key length, and select pointer table. To perform a search, the user sends the device the pointer table to use the Key start position related to the first position in the register the Key starts and the Key length in order to determine the length of the Key to read and the searching operation commences. The device will search the designated pointer table selecting the mid position register first reading that value then going to the Index address for the value read in the pointer table reading the appropriate Key in that register. The device then compares the Target value to the value read from the Index and in the preferred embodiment can perform a binary search going back and forth from the pointer table and the Index until the largest Key smaller than the Target Key has been located. At this point the device can send the read/write head to the band identified from the pointer table, if the data exists is will be located on this band.
Brief Description of the Drawings
FIG. 1 is a pictorial representation of the relationship between the central processing unit host, the device controller, and the information storage device.
FIG. 2 is a schematic representation of an information storage disk having located thereon a plurality of bands in between which user data tracks are located.
FIG. 3 is a pictorial representation depicting the format of a band on the platter, showing a plurality of user data blocks recorded in tracks.
FIG. 4 is a pictorial representation of a single block exploded to show the block header having a physical ID and a user generic Key.
FIG. 5 is a table listing a set of generic Keys, for illustration purposes the generic Key broken down into three specific Keys--the LID Key, the user Key 1 and the User Key 2.
FIG. 6 is a schematic drawing showing the platter surface with a plurality of bands having the user data recorded by proper protocal on the appropriate band.
FIG. 7 is a table showing the method by which the device Index register holds the appropriate Index value for each Index band.
FIG. 8 depicts the sorting scheme for loading the pointer table for the LID Key, the first User Key and the second User Key.
FIG. 9 is a table illustrating the Target Key register, the Select Pointer Table register, the Key Start register, the Key Length register, and the contents of these registers when slight pointer table 1, Select Pointer Table 2, and Select Pointer Table 3 are used.
FIG. 10 is a table showing the searching sequence using the LID Key, the Index and the first Pointer Table.
FIG. 11 is a table showing the searching sequence for the first User Key using the Index and Pointer Table number 2.
FIG. 12 is a table showing the searching sequence for User Key 2 using the Index User Key 2 and Pointer Table 3.
FIG. 13 is a pictorial representation of track C from the illustration showing the successive binary search locations for homing in on the specific track and block to be located.
Detailed Description of the Preferred Embodiment
As shown in FIG. 1, the data to be recorded is first stored in the host central processing unit 1 in its channel interface buffer 2 where it is built up into blocks of data to be transmitted to the device controller 3. In the preferred embodiment, 7904 bytes of information comprise a single block of user data. Once built, the block or blocks are transmitted to the device controller 3 where they are stored in the buffer 4 to be transmitted by the microprocessor 5 to the storage device 6. Once transferred to the storage device 6, the data to be recorded is enabled by the device microprocessor 7 to pass into the device buffer 8 and thereafter onto the disk 9 where it is recorded.
As schematically represented in FIG. 2, the disk format is comprised of a plurality of concentric tracks 10 for the purposes of clocking and for course-fine servo seek operations, as set out in "Optical Disk Data Format Employing Resynchronizable Data Sectors", Ser. No. 534,037, filed Sept. 19, 1983 by Clay, et al, assigned to the same assignee as the present disclosure. In the preferred embodiment, the disk 9 has one Index Band 11 and seven hundred fourteen user bands 12, with each user band 12 having forty eight user data tracks 13 associated therewith as represented in FIG. 3. In the preferred embodiment, each user track 13 can record a maximum of fifteen user blocks 14 of data. The disk Index Band is dedicated to the data indexing function of the device.
Because, in the preferred embodiment, the recording disk is a removeable, nonerasable media, and because with a write once only function, and because the physical location of the data on the disk surface is not known prior to actual writing, it is necessary to place the complete index entries for that disk on that disk itself. Thus, when placed in a new storage device, the contents of that disk can be read and indexing and searching functins performed.
In terms of formatting, the device protocol requires that for any given band, the data for that band be recorded by Key number in increasing order. Thus, on a given band, no block of data which has a Key value smaller than the Key value on a prior recorded block can be recorded. Therefore, on a given band, the second block recorded will always have a larger Key value than the first block, the third larger than the second and so on. However, the bands themselves need not be recorded sequentially. Also, although the normal order of recording in the device is from the outer diameter to the inner diameter, if the user so designates, data will be recorded on any designated band which is available for recording. If the new block of data presented for recording has a Key value smaller than any prior recorded Key value in that given band, the device will place the new user data on a new band to which it can assign an index key less than or equal to the key of the block to be stored.
In operation, as shown in FIG. 4, the host 1 places a generic Key 15 in the header 16 of the user data block 17. The use of a Key in a header 16 is well known, one example being the IBM Key Count System. However, this generic Key 15 is an improvement in that a plurality of specific user Keys of varying length are placed in the generic Key 15 allowing indexing and searching to be done with regard to a plurality of user designated Keys. Once the data is transmitted to the device 6, the device 6 places a physical ID (PID) 18 at the very beginning of the user data 17 prior to recording. This physical ID (PID) 18 is necessary because in the preferred embodiment, when data is optically written on the device, it is a write once only capacity and the host 1 will not know prior to the actual write operation where the data 14 will be physically placed on the disk 9. Thus the PID 18 lists the band 12, track 13 and block 14 within the band, wherein each user block of data 17 will be physically recorded on that disk 9.
As shown in FIG. 4, once the device 6 locates the specific location on the disk 9 surface on which data will begin to be recorded, the Physical ID (PID) 18 of that location is recorded on the disk 9, followed immediately by the generic Key 15 and thereafter the user data 17. In this illustration, digital numerics and alpha letters are used for illustration purposes only. It is understood that the data be recorded is in binary numbers using, for example an ASCII encoding system.
For illustration of the complete functioning of the disclosed invention, as shown in FIG. 5, a table is listed showing the generic Key 15 values for a representative set of user data 14 to be recorded. For illustration purposes, this user data 14 is represented by three separate user Keys. The first Key is a logical ID (LID) Key 19 which is developed by the host operating system to designate which band a given block of information should be recorded and in sequence which block in that band that data represents. (To avoid confusion the reference numerals will be omitted while referring to Key values). For example, for the first entry, LID Key value 00501 indicates the data is to be recorded on the fifth band and that it is the first block of user data to be recorded on that band. Entry 22 shows that user data having LID Key 00406 is to be recorded on band 12 and will be the 6th block of data recorded on band 12. User Key 1 in this illustration simply represents some value in the user data which will be useful to the user in searching for that block of information, User Key 2 shows some other portion of the user data which will be useful in searching for a given block of information. The order in which the items are listed in FIG. 5 represents a random illustration of the sequence in which data could be recorded.
FIG. 6 is an illustration of the recording of the data on the disk 9 showing bands A through G in the sequence in which the data is to be recorded on the disk 9 by LID Key value. That is, item 1 is recorded, followed by item 2, item 3, item 4 and so on, until the last item 30 is recorded. Comparison of FIG. 6, showing the recording by band, with the table in FIG. 5 shows the sequence and order in which data is recorded on the disk 9.
As data is recorded, the device 6 also records, in the Index Band 11, the PID 18 and generic Key 15, if a new file is opened. In the preferred embodiment, this Index band 11 will list only the lowest Key value for a given band 12. Ordinarily, the first Key recorded on a given band 11 will be the lowest Key Value for that band 11. However, should the user decide to delete the prior recorded information on a given band 11, a new set of data can be recorded on that band 11 with a new Key number assigned, this new Key number being lower than the previously recorded (but now deleted) Key Value.
FIG. 7a shows a listing of the Values 22 recorded on the Index band 11 for the data presented in items 1 through 30. Once the data is transferred on the Index band 11 as shown in FIG. 7b, it is read into a random access memory Index 23 in the device. In this preferred embodiment, the Index addresses 24 are the bands 12 upon which the data is recorded, with the individual registers 25 being the complete generic Key 15 value from the Index Value recorded for that band on the Index Band 11. In the preferred embodiment, the values in the index registers 25 are filled in the order in which the data is written on the disk 9. Therefore, shown in FIG. 7b the second register 25 has an address D with a contents 00401, 030, 71 and the next to last entry having an address C with a value 00301, 430, 61.
To accomplish this, as shown in FIG. 8, a set of Pointer Tables are established which have as its register contents, the band Values sorted based upon the Key value associated with that band. For illustration purposes, in this embodiment three pointer tables are used. If a single Key were being used to identify user data, this index could be simply arranged in ascending LID sequence for indexing and searching. However, with generic Keys, said Keys providing the ability to multiply sort user data for searching and indexing, a different, improved method is available. To efficiently use the multiple Keys, additional sets of registers are employed, because it is necessary to break the index down and presort elsewhere in different registers for each set of separate Keys is required.
First an Index Order Table 26 is set up having the same number of positions in its register as there are positions in the Index Register 25. The value in each individual position in the Index Order Table 26 represents the position from which the sort for a given Key should be taken. For example, in position 1, the value number 1 indicates that for sorting the Key 1 you should start with the first position in the index order table and for Key 2 the sort should begin at position 6 in the index order table, and for Key 3 the sort should begin from position 9 in the index order table. This value is represented in FIG. 7c.
As shown in FIG. 8a, the sort for the LID Key which starts at position 1 index is listed in ascending order with the LID value 00101, 105, 51 being the lowest Key Value (recorded on band A), with 00701 560 30 (recorded on band G) being the highest. As shown in FIG. 8b, the Pointer Table 1 for the LID Key thus is arranged in sequence from A through G representing the order of the LID Key values. As shown in FIG. 7c, the sort for the second user ID starts in position 6 with the sort for pointer Table 2 thus being the first value 03071 as found in band D and the highest value being 66021 as found in band E. Therefore, as shown in FIG. 8b, Pointer Table 2 is arranged in the sequence the first value being D and the last value being E. As shown in FIG. 7c, the sort for the third Pointer Table is based on user Key 2 starting with the value in position 9 from the Index Order Table, the first value being 11 associated with band B and the last value being 71 from band D. Therefore, as shown in FIG. 8c, the first value in the pointer table three register is B with the last value in the pointer table represented as D.
Having set up the index and sorting registers, a user can now use the extended index and the rapid band searching functions to search for a given block of user data on the disk. For illustration, the search will be for item 12 on the list of user data from FIG. 5 with LID value 00304, first user Key value 406 and second user Key value 64. FIG. 9 shows the Target Key value for user data to be located and read from the disk. As shown in FIG. 9, to conduct an index search using the generic Key, a Target Key register, a Select Pointer Table register, a Key Start register, and a Key Length register are placed in the device random access memory. The Target Key register holds the value of the Target Key to be searched for comparing with the results of the index and rapid band search. The Select Pointer Table register holds the value for the particular pointer table for which the search will be conducted. The Key Start register holds the value of the position in the Index from which the first value position in the Index Register the Key Value for searching will be selected. The Key Length is the number of characters in the Key Value selected for searching.
For illustration, all three Key values for item 12 will be taught. In searching using the LID Key as shown in FIG. 9b, the Target Value is set in the Target Key register, with the select Pointer Table set to 1, representing the search using the LID Key, the Key Start placed at 1 which is the position where the LID Key starts in the index and the Key Length having a value of 10 representing the number of positions in the entire register starting from the first position. With the registers filled as provided, the search can be initiated.
In operation, the device selects the middle value from pointer table 1. In this case, as shown in FIG. 10 value D. The device then goes to address D in the Index and reads the contents of the register at that address, the contents being the Key value for band D. The device then compares the selected Key Value with the Target Key Value, using as a search criteria: finding the largest Key in the Index that is smaller than, or equal to, the Target Key value.
Using this criteria, in the preferred embodiment, a binary search is conducted in the pointer table. For example for the LID Key, the value selected is D. The contents in the index at address D are read and compared to the Target value. In this case 00401 030 71 is greater than 00303 450 64, and because a pointer table is laid out in increasing sequence, the device selects a value in the pointer table between the first entry and the middle value, thus moving upward in the pointer table. As shown in FIG. 10, the value B is selected and the contents of address B and the Index are read. In this case, 00120 130 11 is less than the Target value 00303 450 60. However, the device must see if there is a larger Key Value in the Index that is still less than the Target Key value. Therefore, the device moves downward in the pointer table, in this case to the value C. The device goes to the Index and reads the contents of the register whose address is C, finding 00301 430 61 which is less than the Target value but greater than the contents from address B. Since the contents of address D have already been searched and compared, the device knows that if the data exists, it will be located on band C.
Showing now a search using the first user Key, as shown in FIG. 9c, the Select Pointer Table is set to a value of 2, indicating that the second Pointer Table is to be used for the search. The Key Start is set to 6, thereby indicating that the search through the Index should start at position 6 for comparing with the Target value from position 6 on. The Key Length is set to a value of 05 indicating that 5 digits in the index should be read starting from position 6 in order to find the Key value to be searched.
In operation, the device again selects the middle value in pointer table 2 in this case B. The device then reads the contents of the register associated with B starting at position 6 through position 10 reading 130 11 and comparing that with the Target value of 450 64. Since the selected index value is less than the Target value, the device moves downward in pointer table 2 selecting the address G, the contents being read in the index as 560 31 which is greater than the Target value. The device therefore moves upward in the table in this case to address C, which in the index has a value of 430 61 which is less than the Target value. However, since address G has already been searched, the device knows that if the data exits it is located in band C.
Turning now to a search using the third user Key as shown in FIG. 9d, the Target Key register is set to 64, the Target Pointer Table set to 3, the Key Start set to 9 and the Key Length set to 02. In operation as shown in FIG. 10, the device selects the Pointer Table value F, reading the contents of the index as 41. This value is compared to the Target value of 63, this value being greater than the index value the device moves down to the Pointer Table value of C. The device then compares the contents of the index at address C comparing that to the Target Value. This value is less than the Target value, however, the device is looking for the largest Key smaller than the Target value, so the device moves up to address A, the contents of address A are read as 51 which is less than 63 but since the value in address C is larger than the value in address A, the device selects C as the largest Key smaller than the Target value, knowing that if the data exists it will reside on band C.
Therefore, regardless of which of the selected Key values used for the search, the same band is identified as the location of the data desired. The advantages of the generic Key become more readily apparent in that the user is able to search for a given data block using a plurality of different user Keys to identify said data. For example, user Key 1 could be social security numbers while user Key 2 could be city or state locations allowing the rapid index searching for a given set of data using different identification parameters.
Once the band on which the data resides has been identified, the device can initiate a rapid band search in order to find the specific block of information desired. In the preferred embodiment, it must be understood that there are 15 blocks of data per track and 48 tracks per band for a total of 720 user blocks on a given band so that reading the header information in each block individually across the entire band can be time consuming and inefficient. In operation, the device sets, as a first value, a low boundry value which is equal to 1, and a second value as a high boundry value equal to 48 (thereby covering all 48 data tracks on that band). The median is then calculated, with the device sending the read/write head to that median track.
The device then reads the header information containing the generic Key for that block, comparing the read value to the Target value. If the read value +1 is greater than the Target value, then the lower boundry value is set equal to the track number on which the read/write head is tracking. Conversely, if the read value +1 is less than or equal to the Target value, then the higher bound value is set equal to the value of the track upon which the read/write head is tracking. In either case, the device can then recalculate a new median, sending the read/write head to the new median track, reading the header information on any block on that track, and comparing the Key value read to the Target value. This process is continued until the device has homed in on one of two tracks, at which point the header information of each block is read from the start of the Lower Bound to the end Upper Bound track the data block being sought somewhere in between. Turning now to our example, we see that in band C, for illustration purposes, as shown in FIG. 6, 6 blocks of data have been written in band C. The device sends the device read/write head to the desired band, in this case band C.
In example, as shown in FIG. 11, using data band C, for illustraiton purposes using the first user Key, between the upper bound and lower bound, a median is calculated and the first block being read. In this case user block number 29 is read as 480 66 since this value is greater than the Target value, the upper bound made this new track with a median found between this new upper bound track 24 is made the upper bound where the median calculated between track 24 and track 1. Track 12 is read, the first block showing a Key value of 440 62. Since this value is less than the Target value, the device sets the lower bound equal to track 12 and finds a median between track 24 and track 12. The first block readable on track 18 is read, finding data block 470 65. Since this value is greater than the Target value, the upper bound is set to 18 and the median between track 12 and track 18 found as track 16. Track 16 is read the first block readable having a value of 450 63 this value less than the Target value. The device will then read a key from track 17. At this point, the device knows that at the location on track 18 where block Key 470 65 was read and track 16 where block 450 63 was read, the Target value, if on this disk, the device knows that the information sought if it exists, is within this two track area, thereby initiating a block by block read of each block after block 450 63 inward until the block having the lowest valued key which is greater than or equal to the Target Value is found. At this point, the device will signal the controller and thereby the host that the locate operation is complete and the data sought to be read is available for reading.
While the disclosed invention has been discussed with regard to a relatively simple binary search, it should be understood that any number of searching algorithms may be used to implement and practice the disclosed invention, and that the disclosed procedures are in no way intended to limit the scope of the appended claims.
Claims
We claim:
1. A method for indexing and searching user data recorded in block format on an information recording disk having an index band and a plurality of user bands, each of the user bands having a plurality of user data tracks within which the respective blocks of user data are recorded, wherein the disk is disposed within an information storage device, including a microprocessor and a random access memory, in communication with and responsive to instructions from a host computer, the method comprisisng the steps of: validating first an instruction from the host computer to write a block of user data to a predesignated user band, said first validating step including the steps of checking for the availability of recordable space within said predesignated user band, issuing an error instruction to the host computer upon the contingency of no available recordable space within said predesignated user band, and otherwise assigning to said block of user data a first key value that is indicative of a plurality of preselected identifying factors, including the identity of the particular user band upon which said block of user data will be recorded, which are unique to said block of user data; writing first said block of user data with an associated header containing said first key value to said predesignated user band; validating second an instruction from the device, issued upon the occurrence of said first writing step, to write to the index band a third key value, said second validating step including the steps of checking for the presence within the index band of a second key value associated with said predesignated user band, and determining the lower of said first and second key values, said second key value constituting said third key value when said second key value is both present within the index band and lower than said first key value, otherwise, said first key value constituting said third key value; writing second said third key value on the index band; entering a plurality of lowest key values into a plurality of index registers within the random access memory, each of said plurality of index registers corresponding to a respective one of said plurality of preselected identifying factors, and each of said plurality of lowest key values representing at least one of said plurality of preselected identifying factors while corresponding to a part of said third key value associated with the respective user bands; searching said index registers, upon the occurrence of an instruction from the host computer, for a fourth key value, said fourth key value constituting the largest of said plurality of lowest key values entered into said index registers which is less than or equal to a target key value denominated by the host computer; and informing the host computer that the particular user band on which the target key value was recorded has been identified.
2. A method for indexing and searching user data as recited in claim 1 wherein the step of searching said index registers is comprised of the steps of: sorting a plurality of index addresses in a pointer table, said addresses sorted by its corresponding lowest key value; selecting the median value in said pointer table, said median value representing the respective one of said addresses; comparing said target key value to said lowest key value for the median address selected, using the protocol moving upward or downward in said pointer table predicated upon a search for said fourth key value, until the largest of said plurality of lowest key values smaller than said target key value as found.
3. A method for indexing and searching user data on an information recording disk as recited in claim 1 wherein the information recording disk is an optical recording disk.
4. An apparatus for indexing and searching user data recorded in block format on an information recording disk having an index band and a plurality of user bands, each of the user bands having a plurality of user data tracks within which the respective blocks of user data are recorded, wherein the disk is disposed within an information storage device, including a microprocessor and a random access memory, in communication with and responsive to instructions from a host computer, said apparatus comprised of: first validation means, responsive to an instruction from the host computer to write a block of user data to a predesignated user band, for checking for the availability of recordable space within said predesignated user band, for issuing an error instruction to the host computer upon the contingency of no available recordable space within said predesignated user band, and for otherwise assigning to said block of user data a first key value that is indicative of a plurality of preselected identifying factors, including the identity of the particular user band upon which said block of user data will be recorded, which are unique to said block of user data; first recording means for writing said block of user data with an associated header containing said first key value to said predesignated user band; second validation means, responsive to an instruction from the device to write to the index band a third key value, for checking for the presence within the index band of a second key value associated with said predesignated user band, and for determining the lower of said first and second key values, said second key value constituting said third key value when said second key value is both present within the index band and lower than said first key value, otherwise, said first key value constituting said third key value; second recording means connected to said second validation means for writing said third key value on the index band; a plurality of index registers connected between the host computer and the device having entered therein a plurality of lowest key values, each of said plurality of index registers corresponding to a respective one of said plurality of preselected identifying factors, and each of said plurality of lowest key values representing at least one of said plurality of preselected identifying factors while corresponding to a part of said third key value associated with the respective user bands; a means, connected between the host computer and said plurality of index registers, for searching said plurality of index registers upon the occurrence of an instruction from the host computer for a fourth key value, said fourth key value constituting the largest of said plurality of lowest key values entered into said plurality of index registers which is less than or equal to a target key value denominated by the host computer; and a means connected to said searching means for informing the host computer that the user band on which said target key value was recorded has been identified.
5. An apparatus for indexing and searching user data as recited in claim 4 wherein the means for searching said index registers further comprises: a means for sorting a plurality of index addresses in a pointer table, said addresses sorted by its corresponding lowest key value; a means connected to said sorting means for selecting the median value in said pointer table, said median value representing the respective one of said addresses; a means connected to said selecting means and said sorting means for comparing said target key value to the said lowest key value for the median address selected, using the protocol moving upward or downward in the pointer table predicated upon a search for said fourth key value, until the largest of said plurality of lowest key values smaller than said target key value is found.
6. An apparatus for indexing and searching user data on an information recording disk as recited in claim 4 wherein the information recording disk is an optical recording disk.
Patent Citations (2)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3670310 | 1972-06-01 | Bharwani et al. | |
| US3913074 | 1975-10-01 | Homberg et al. |