Suppose that we have a Table A with only one column A1 which is indexed by B-tree. What is the cost of running query "Select count(*) from A where A1=10"
I think is O(LogN), is that right?
The actual complexity depend on DBMS realization. However, I do not think it is O(Log N). This formula is correct for searching for one line in a table. First, the DBMS selects lines from a table, then it counts them. Number of the selected is equal to the number of occurrences which is 0..N. If there are 0 or 1 occurrences then the complexity is O(Log N). After finding the first occurrence, the algorithm must check if there are more occurrences. In a tree, this operation is performed in a single step. But algorithm must repeat this single step at least as many times as many occurrences. If there are more than 1 ones, it is probably O(M + log N) where M is quantity of occurrences or less than this value but more than O(log N). If M is small (in comparison with N) then the complexity is O(log N).
Hi Lev, thanks for answer
What about sorting cost when A1 column is already indexed by B-tree?
Sort costs O(N logN), O(N) or O(LogN)?
Somewhere I read B-tree keeps the keys ordered. Thus I cant use the method 2 in the this approach: http://www.geeksforgeeks.org/count-number-of-occurrences-in-a-sorted-array/ ?
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs