>>Geo,
>>
>>>LOCATE is a sequential search of the table. SEEK utilizes indexes which are binary trees ordering the table.
>>
>>I'm not debating that SEEK is faster -- but how can LOCATE always be a sequential search of the TABLE, even when Rushmore kicks in?
>
> When I use a LOCATE command the speed of the command is unaffected by the presence(or lack thereof) of indexes. Thus, I suspect LOCATE does not use RUSHMORE.
LOCATE will use Rushmore optimization as long as the FOR expression matches the key expression(s) of tags in the CDX for the table(s) involved. Keys that contain a FOR clause cannot be used for Rushmore optimization.
> I believe LOCATE performs a sequential search because when I LOCATE for a record that is the 50th record in a table of one million records the search time is very short ( less than 1/10 of a second). However, when I perform a LOCATE so that it finds record 999,999 the search takes over one minute.
If a sequential search takes place, then the time to reach a matching record varies by the number of records that must be examined to identify that record. If the FOR condition is fully or partially Ruushmore optimizable, then Rushmore is used to select a set of eligible records before examining the set record by record for positioning, which will result in LOCATE times not varying in a linear fashion based on relative position.
Performing a non-optimizable LOCATE on a table with an active index creates the worst possible search performance, because the file is scanned record by record in the index-specified order; the index must be examined to determine what the 'next' record would be.
> SEEK search times are always the same regardless of where the correct record is inside the table.
>
That's because the index only is consulted, and the number of examinations required to determine the presense of a specific value varies logarithmicly, never exceeding a very small number of compare operations to complete, based on the depth of the b+ tree that implements the index.