🚀 go-pugleaf

In general, this is one of the classic problems of computer programming: placing data in a structure so that it can be searched efficiently.

There are many time-tested methods of solving this issue, each with their own plusses and minuses:

- VSAM KSDS. This is similar to Ed's idea of isolating the data and the keys, with the addition of the concept of CI and CA splits.
- HASHing. This has been implemented by IBM and others, one example being IMS HDAM data bases. Using a good randomizer, it can be fast. Disadvantages include the possibility of long synonym chains.
- Binary search. The difficulty here, of course, is the issue of insertions and deletions, which can be handled with various techniques, including multi-level searches, etc.
- Serial search. Performs poorly for large numbers, but easy to do insertion.

The developer has to determine the ratio of retrievals to insertions/deletions, likely size, performance requirements, time to implement and debug, and select an appropriate design.

Tom Harper

-----Original Message-----
From: IBM Mainframe Assembler List
[mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU]On Behalf Of Edward E. Jaffe
Sent: Friday, September 30, 2005 11:48 AM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: Shifting memory to the right


Michael Stack wrote:

> If you're going to do a binary search, why not use a balanced binary
> search
> tree?  If a tree node is a row, your link memory overhead would be
> relatively small and your search time would be comparable.  And if you
> are
> not inserting too many rows, the overhead for balancing should be small,
> too.  A lot less virtual (and real) memory used, as well.
>
> It's usually (!) less costly to manipulate a data structure than to move
> data around.  YMMV.  See Knuth, TAoCP, Vol 3, 2nd Ed. (Sorting and
> Searching) pp 471-473 for a discussion of using a balanced tree to
> represent a linear list.


In addition, if the search keys themselves are relatively small and
represent a small percentage of the total storage for each table entry,
it might make sense to place a copy of the keys into the tree structure
rather than always using the data pointer during the search. Avoiding
access to the real data when performing the search can help keep the
working set to a minimum. If the keys are large, this approach probably
isn't worth the extra storage requirements for the tree structure.

--
...-----------------------------------------------------------------.
| Edward E. Jaffe                |                                |
| Mgr, Research & Development    | edjaffe@phoenixsoftware.com    |
| Phoenix Software International | Tel: (310) 338-0400 x318       |
| 5200 W Century Blvd, Suite 800 | Fax: (310) 338-0801            |
| Los Angeles, CA 90045          | http://www.phoenixsoftware.com |
'-----------------------------------------------------------------'