Table without index, data save on non-order structure. When you want to search for some data, it would use the "Scan" to go check through all the data from start till end on the table.
Case 1: query table without index, query 1 record,
SQL query plan step: "table scan" all data, O(N)
Case 2: query table without index, query many records,
SQL query plan step: "table scan" all data, O(N)
Table with index, data will save on B-tree structure, which when you want to search for 1 data (on the indexed column), it would make use of the B-tree structure to find the data.
Case 3: query table with on indexed column, query 1 record,
SQL query plan step: "index seek", O(LogN)
Case 4: query table with on indexed column, query many record,
2 possible, the SQL Query Optimizer will made use of the "index statistics" to compute and determine which action step is faster to be use.
- (a) SQL query plan step: "index Scan", O(N)
- (b) SQL query plan step:
"index seek", O(R LogN) [R for number of records]