ap.b-trees Article/Article


Command ap.b-trees Article/Article
Applicable release versions: AP
Category Article (24)
Description discusses using Advanced Pick B-Trees and other advantages of Advanced Pick.

Contributed by Terri Hale
(original article ran in PickWorld Magazine)

In my travels over the past couple years spreading the gospel of Advanced Pick (AP) to Pick user groups and students in training seminars, I've been asked "What would I gain by switching to AP?"

There are many features which warrant the upgrade. I particularly like the Update processor for data entry and retrieval. Another feature which I've become increasingly dependent on is the tcl-stack. Level pushing is a feature which I'd rather not live without. Unlimited item size is great. Furthermore, prototyping application software can be done in a few hours or less using UP and all the new processing codes.

But, this article will focus on one feature which I feel justifies the upgrade (or new installation) above all others. This single feature is AP's implementation of indexes or B-Trees. Let me explain the merits and clarify some common mis conceptions regarding this feature.

Index Maintenance & Housekeeping

AP's indexes need to be created once and only once using the create-index verb. The syntax for this TCL statement is:

create-index filename a.code

Any (or) all attributes in a file can have an index created. But, not all data fields lend themselves to indexing. The only limitation to the number of indexes that can be created is disk consumption.

The size of the index consists of the length of the header, key, and item-id, the number of nodes and the number of items in the file. To find the number of frames used in an existing index, the verb nframe-index is available. The syntax for this TCL command is:

nframe-index filename a.code

An "*" can be substituted for the a.code to find the size of every index on a file.

Once the index has been created, the system AUTOMATICALLY updates the index each time the file is updated. This includes updates which occur when loading items into a file (with the t-load verb), deleting items from Pick/BASIC or UP and copying items into a file (using the copy verb).

If you suspect a corruption in an index, you can validate its integrity using the verify-index verb. The syntax for this verb is:

verify-index filename a.code

If there is a problem with the index, you can delete it and then recreate it. The syntax for deleting the index is: delete-index filename a.code

Saving Indexes

You CAN save the indexes on a file-save. In initial releases of AP there was no option to save the indexes. But in the current releases, the indexes can be save by using the "B" option on a file-save. Now you can either save the indexes or regenerate them after a restore. Dealer's choice.

Pick/BASIC and Indexes

You CAN access the indexes from Pick/BASIC as well as from the Update processor. Think about the impact of using the indexes from Pick/BASIC for a moment. For your existing applications written in Pick/BASIC, you could tie into the AP indexes and experience immediate update and retrieval of data. No more cross reference files or inverted lists to be periodically regenerated.

Access and Indexes

On the retrieval side of things, the verbs sselect, sort and list utilize the index if there is an index corresponding to the sort key. For example, consider an index on the customer.name field in an orders file. I executed the following statement:

sort orders by customer.name

on my Compaq portable 286. This report took 3 seconds to begin output (in a file of 411 items). When I removed the index and executed the same command, output began after 10 seconds.

Using B-Trees from the Update Processor

Let's build a dictionary item in the orders file called customer.name to demonstrate how to use indexes with the Update processor. This dictionary will allow us to look up values (names) in the customer file and also allow us to search through our orders file for specific customer orders.

The first step to using indexes is the creation of the index. For our example we would need an index on attribute 1 of the orders file.

create-index orders a1

Since we are also going to access a remote index in the customer file, we also must have an index created on customer attribute 1.

create-index customer a1

When using B-Trees with the Update processor, you MUST define an index correlative on the input-conversion attribute of the dictionary. There may be one (local or remote) or two (one local and one remote) index defined in the dictionary.

See the following table for the dictionary item called customer.name in the orders file.

DICT orders 'customer.name'


dictionary-code a
attribute-count 1
substitute-header name
output-conversion tcustomer.file;x;;1
attribute-type l
column-width 10
input-conversion i

"i" is a "local" index on the name attribute and is used to locate existing orders for this customer. To use, type in

"string" control<f> = forward search control<d>=backward search

"icustomer;a1" is a remote index on customer(name). Used to locate valid customers. To use, type in

"string" control<u>=forward search control<y>=backward search

macro name address zip

Default input attributes used when zooming to the customer file.


To get into the orders file we will use the UP command:

u orders customer.name

orders NEW ITEM
customer.name _

At the customer.name prompt, the user can enter a partial name and then either search the customer file (<ctrl>+u, <ctrl>+y) for customers whose name begins with the string entered or search the orders file (<ctrl>+f, <ctrl>+d) for exist ing orders whose customer.name begins with string entered. Results are immediate. No waiting.

Using B-Trees from Pick/BASIC

As mentioned above, the index must have been created prior to accessing the index from either Pick/BASIC or UP. If we haven't already created the index we would do so as follows:

create-index orders a1

The Key and Root (see below) are two new statements in Pick/BASIC which allow the programmer to access indexes.

root filename,a.code to root.variable {then..else statements}

When the create-index verb is executed, the system puts the root frame address in the file-defining item on the correlative attribute. The root statement grabs this address (root.variable). This root.variable is used by the subse quent key statement. The a.code must be in the same format as the create-index verb.

key('operator',root.variable,index.key,item.id) {then..else statements}

The key statement must be preceded by the root statement. The components are defined as:

operator description

'c' Will return an index.key on an exact match or the next higher index.key and item-id. Normally this operator is used first to get the initial item and then another key statement using the 'n' operator is used to get the NEXT item.

'n' Will return an index.key on an exact match or the next higher index.key and item-id. This is generally used in a loop construct when searching for all items that match the search criteria.

'p' Will return an index.key and item-id on the previous item. Similar to 'n' but the search is backwards. This is also helpful to use in a loop construct to get the last 'n' number of items.

'r' Will only return an index.key on an exact match.

'v' Used to verify the index if a corruption is suspected. It will locate a given index.key and item-id and verify that the pre-defined item-id equals the item-id returned.

root.variable This variable contains the address of the index obtained by the previous root statement.

index.key This variable contains the string being searched for. It must be pre-defined before using the key statement. If the string is found, the results are returned into this variable when using the 'c', 'n' or 'p' operators.

item-id This variable will be assigned the item-id of the item that contains the index.key. The item-id MAY be preassigned when using the 'p' or 'n' operators. It MUST be preassigned when using the 'v' operator.

"then..." Is executed if the item-id is found or if the index.key verifies with the 'v' operator.

"else..." Is executed if the item-id is not found or if the index.key does not verify with the 'v' operator.

The following Pick/BASIC program will search the customer file for all people whose name begins with 'terri'. It will then print the customer's name and phone number:

* Program to find and print all names
* beginning with 'terri'
file customer
root 'customer','a1' to customer.root else
stop 'Index not available'
customer.name = 'terri'
key ('c',customer.root,customer.name,id) then
loop while customer.name[1,5] = save.name do
read customer from id then
crt "customer= ":customer(name):' ':customer(phone)

Running this program on my customer file yielded three items in one second. Compare this to using the following Access statement:

list customer with name = "terri]"

The speed of retrieval using indexes in Pick/BASIC is most impressive when accessing very large data files. Output occurs instantaneously regardless of the size of the file.

Whether the reader has already installed Advanced Pick or is contemplating purchasing the product, I encourage you to investigate the benefits to your organization of utilizing AP B-Trees.