A B-tree implementation of MUMPS global arrays using variable length keys

MUMPS, (Massachusetts General Hospital Utility Multi-Programming System), was first developed in the mid 1960's as a high-level interpretive programming language. MUMPS was designed to facilitate the creation of conversational programs that would permit dynamic data base interaction in the clinical environment. The files that contain the data base are hierarchically organized tree file structures called "global arrays".

As with any data base management facility, the requirement to service an interactive user is highly dependent upon the speed with which a given token of information can be stored, deleted, and retrieved from its peripheral storage location. This paper describes a B-tree data structure implementation of MUMPS global arrays with variable length keys.

The B-tree data structure was first developed by Dr. R. Bayer and Dr. Ε. Μ. McCrieght in the early 1970's. This data structure allows any random number of key insertions or deletions to be performed upon the tree structure without disturbing the excellent benefits gained from having a balanced tree. Their work dealt with a tree structure of nodes which contained the obstacle of fixed length keys. In this project the basic B-tree algorithms are followed, but with new modifications made to allow variable length keys inside the B-tree node. This modification in some instances has been found to lead to a better disk space allocation.