Someone at our place came up with a fairly slick solution for this about 30 years ago. Design was to get around paging and a desire to not allocate multiple buffers for a dynamic table in a TP system. Another one we use daily.
One large block. Key data is pulled from the record and built into a sorted binary searchable table with entry length of key + 3 at the top of the buffer. Inserts move end of table down. The + 3 is the displacement to the rest of the record minus the key. First two bytes of record are length of non key portion. This is inserted into the same block, filling from the bottom up. When the pointers intersect the table is full. We can reorganize if necessary at that point to fill holes from deletes. Careful tuning means we don't hit this often. We have one other that we use for very large tables that are fairly static and built mostly up front. We cache security info in it. Here we build a sorted array but add space for a forward pointer. On completion we turn the array into a linked list with each pointer linked to the entry's neighbor. Initial search is binary, but if pointer <> next then we traverse list for insert point. A CS is all it takes for an add - out of sequence stuff is shoved in next free slot in overflow. That too works well for our use case. Sent from my iPad > On Oct 24, 2013, at 5:45 PM, "Tony Thigpen" <t...@vse2pdf.com> wrote: > > After a couple of posts about my post, I will go back to my point. > > You can only binary search a fixed length table. If you create an index > table, the index table is the actual table being searched, not the > original table. > > Now, Robert does have mention a neet trick where the fixed table > contains a refference pointer to the actual data to be compared. But, > the pointer table is still a fixed length table. :-) > > You just can't binary search a variable length table. > > Tony Thigpen > > -----Original Message ----- > From: Robert A. Rosenberg > Sent: 10/24/2013 05:12 PM >> At 12:45 -0400 on 10/24/2013, Tony Thigpen wrote about Re: Linear >> search vs binary: >> >>> All entries will be fixed length. Can't really have variable length and >>> use a binary search. >> >> That depends. If the table you are sorting is a table of pointers to >> the actual data (and is ordered by the compare field), the entries >> can be variable length so long as the compare field is fixed length >> and is preceded by an entry length field. You use the pointer to find >> the compare field of an entry and once you find the correct entry, >> you back up to the location of the entry length and can then use the >> entry. >> >>
