Which is more efficient b+ tree or search (binary or linear)? SELECT A
FROM T
WHERE M &gt; 1000 AND M &lt; 5000;


I am unable to judge which of the below is best suited for the above query:


Linear search
Binary search on M
B+-tree with index on M
B+-tree with index on A


Which is the best answer and why?

I faced this question recently in an exam and I couldn't find the solution. I chose option 3 (B+ tree with index on M) because the query is not sorted on M and B+ tree indexing on A will make it difficult compared to M (I guess).

I want some clarification of the concepts, because I am a little confused about when each of the above can be effectively used.

To be more clear: when a query optimizer chooses optimization plans which of the given options will it pick? That is what the intention of the question was.
Let us consider a dataset with N items, of which P items match the predicate and will be returned by the query.

1a.A linear search, unsorted data. There is no way for the algorithm to know whether a value will match the predicate until that value is read. Therefore the only solution is to read all values and ignore those which do not match the predicate. The effort will be O(N).

1b.A linear search, data sorted by M. In this case we are assured that all values which match the predicate are contiguous in the data. However, there is no way to know the offset of the first value so, again, reading from the beginning is the only approach. Once a value is read that is larger than the upper limit the algorithm can stop. So, in general, this approach is faster than the unsorted approach. It is still O(N), however.

2.Binary search on M. A binary search requires the data to be sorted. Finding the lower/ upper boundary will require fewer operations - it is an O(log N) algorithm. Reading all the values between the lower and upper bound is O(P), however, so overall that is the query's complexity.

3.BTree index on M. In this context a BTree is a more general form of the binary search. Both operate by eliminating a fraction of the possible results in each itteration of the algorithm. This fraction is known as the fan-out. For a binary search the fan-out is 2 i.e. 1/2 the values remain after each itteration. For a BTree the fan-out is determined by the number of index rows that can be held on a data page, which is typically much larger than 2, and so specific values can be found in fewer itterations. The complexity is the same, however, at O(log N) to find the lower limit and O(P) to read the values.


BTree on A. This will be useless as the query puts no restriction on A's value.



  when a query optimizer chooses optimization plans which of the given options will it pick


It will pick the cheapest one. It is the optimiser's job to examine various physical implementations of the query (use and index, scan all rows, sort the data etc), apply heuristics to assign a cost to each permutation and deliver the cheapest (in terms of estimated elapsed time) to the execution engine as a query plan. Note that the cheapest need not be the least complex in Big-O terms. Big-O notation shows how the effort required changes as the number of items approaches a very large limit. Most databases, however, do not have an infininte number of rows. The optimizer has information about the actual number and distribution of values within the dataset. These are stored in internal statistic objects.

Let's take an example where we have a BTree on M which is 3 levels deep. The full table occupies 1,000 pages on disk. Remember that all data movement happens one page at a time. If the given query were likely to return only a single row it would be efficient to use an index on M to read four pages in total (3 from the index on M and one from the table to get the corresponding value of A). On the other hand, if the statistics suggest that most of the data pages will be read it will be more efficient to ingore the index and scan all data pages, ignoring the ones which do not match the predicate.

I have never heard of binary search implemented in a DBMS. BTrees offer the same functionality with greater performance.

Linear search (also known as a table scan) will be used either when no index exists, or when the overhead of using the index is more than the benefit of identifying individual rows.

BTrees are not the only type of index. Single-value lookup and table scan are not the only possible algorithms.