00010: Description of MKEYED files: Bayer b-tree

Title:

Description of MKEYED files: Bayer b-tree

Description:

Here is a brief summary of MKEYED files: 

The basic structure is that of a Bayer b-tree, with each node in the key structure containing one or more keys. No node in the tree other than the root node is permitted to be less than half full. This is necessarily a balanced tree, balanced in the computer science sense that no leaf is more than one level deeper than any other leaf. Each keychain that you create is its own chain of key nodes, with its own root pointer in the header of the file. 

The size of the keynode is partially chosen by the size of the keys in the file–a key greater than 64 bytes in length will cause a blocksize of 1024 to be used, else a blocksize of 512 bytes will be used. The blocksize is the same for all keys and records in the file. A key node is always one block in length. Records in a dynamically allocated file are allocated in “clusters”, the size of a cluster is a multiple of the file’s blocksize less than 8KB. The cluster size is chosen to waste as few bytes per allocated record as possible. Records greater than 8K in length are allocated on an individual basis. 

Key nodes that are freed as records are removed and the key tree collapses are recycled, same are records are recycled after removal. 

Q&A 

1. Does the mkeyed b-tree structure balance itself automatically, such that sequential adds yield reasonable depth? 

Yes. A tree will never be more than one level out of alignment with itself. 

2. Are there any measures you can/need take to avoid excessive depth in secondary key chains? 

No, the algorithm handles this automatically. 

Last Modified: 11/10/1998 Product: PRO/5 Operating System: All platforms

BASIS structures five components of their technology into the BBx Generations.