|
How To Insert New Records Into a Sorted Table
|   |
|
How To Insert New Records Into a Sorted Table
| |
Problem: How To Insert New Records Into a Sorted Table
Solution: For optimal performance when working with tables that have large numbers of records (for example a table of 10000 barcoded inventory items), it is advantageous to keep the table records in sorted order, so that the Tables().BinarySearch function can be used to locate a specific record quickly. If you create a new record in that table, a standard approach is to then re-sort the table using Tables().QuickSort so that the new record is placed into the correct sorted position, once again enabling the use of the BinarySearch function to locate records quickly. The QuickSort function takes more and more time as the number of records increases. This article describes an alternate approach to keep your table sorted when adding new records without requiring a QuickSort, thereby yielding even better performance.
The general approach for this method is to (1) find where the new record should go into the sorted table first, (2) create the new record at the end of the table, then (3) move that new record into the correct sorted position.
How do we easily determine where the new record should go in the sorted table? Simple: the BinarySearch function will tell us! The BinarySearch function returns True or False to indicate whether a match was found. If a match is found, the RowNum parameter will be set to the row number where the match was found, but if a match is not found, then RowNum will be set to the row number where a match *should* be found if there was one! This is the correct sorted position for that item if it is added to the table. That is where the item would go if it was added to the table and then a QuickSort was called. We can take advantage of that information to put a new record into the right location without needing to sort the table again.
Let's use a simple example where you are taking inventory by scanning barcodes of items on a shelf. If that item already exists in the database, then scanning it will increment the quantity by one. If that item is not located in the database, then a new record is created and the quantity is set to 1. A real inventory application might be a little more complex, but this will do for the illustration of the concept.
We want the best performance when taking inventory, so we'll keep our item database sorted on the barcode number, allowing us to use the fast BinarySearch to locate scanned items in the table. So, we scan in the item barcode, then call the update/create script code in our barcode handler event, like this:
'search for the matching item (in strBarcode variable) in our database (ItemCode field in tItems table)
'BinarySearch on sorted table yields best search performance
dim bFound, RowNum
bFound = Tables("tItems").BinarySearch("ItemCode", true, strBarcode, RowNum)
if bFound = True then
'position to the matching row in table
Tables("tItems").Position = RowNum
'increment item quantity (ItemQty field)
Tables("tItems").Fields("ItemQty") = Tables("tItems").Fields("ItemQty") + 1
'play loud boop-beep audible confirmation tone
Tone(1500, 75, 64)
Tone(2500, 75, 64)
else
'create new item record and set Qty to 1
Tables("tItems").CreateRecord
Tables("tItems").MoveLast
Tables("tItems").Fields("ItemCode") = strBarcode
Tables("tItems").Fields("ItemQty") = 1
'move new record into correct sorted position without needing to QuickSort!
Tables("tItems").MoveRecord(RowNum, Tables("tItems").Position)
'play loud boop-bee-bee-beep audible confirmation tone
Tone(1500, 75, 64)
Tone(2500, 50, 64)
Tone(2500, 50, 64)
Tone(2500, 75, 64)
endif
Since you've either updated an existing item quantity or added a new item and placed it into the right sorted position, there is no need to sort the table again, and you can quickly get on with the job of scanning the next item.
Keywords: QuickSort, sort, BinarySearch, search, find, locate, speed, performance, MoveRecord, inventory
KB ID: 10087
Updated: 2008-06-26
Satellite Forms KnowledgeBase Online