Branch Table - Creating The Index For The Branch Table

Creating The Index For The Branch Table

Where there is no obvious integer value available for a Branch table it can nevertheless be created from a search key (or part of a search key) by some form of arithmetic transformation or could simply be the row number of a database or the entry number in an array containing the search key found during earlier validation of the key.

A hash table may be required to form the index in some cases. However, for single byte input values such as A-Z (or the first byte of a longer key), the contents of the byte itself (raw data) can be used in a two-step, "trivial hash function", process to obtain a final index for a branch table with zero gaps.

1. Convert the raw data character to its numeric equivalent (example ASCII 'A' ==> 65 decimal, 0x41 hexadecimal)
2. Use the numeric integer value as index into a 256 byte array, to obtain a second index (invalid entries 0; representing gaps, otherwise 1, 2, 3 etc.)

The array would be no larger than (256 x 2) bytes – to hold all possible 16-bit unsigned (short) integers. If no validation is required, and only upper case is used, the size of the array may be as small as (26 x 2) = 52 bytes.