Single record access incurs the costs listed in Table 7.4. As already mentioned for
LOOP ... WHERE, a linear share is added for duplicates in the binary search for the
index tables, which can exhibit a linear runtime behavior in extreme cases (all
entries relate to the duplicates key).
Standard Sorted Hashed
READ ... INDEX O(1)
Constant
O(1)
Constant
–
READ ... WITH KEY ... (Complete
key)
O(n)
Linear
Binary search:
O(log n)
Logarithmic
O(log n)
Logarithmic
O(1)
Constant
READ ... WITH KEY ...
(Incomplete key, initial part)
O(n)
Linear
Binary search:
O(log n)
Logarithmic
O(log n)
Logarithmic
O(n)
Linear
READ ... WITH KEY ...
(Incomplete key, no initial part)
O(n)
Linear
O(n)
Linear
O(n)
Linear
Table 7.4 Costs for Reading Single Rows from Internal Tables