asked on

database operation big-O complexity

I see databases use unique keys to access the data comprising a record. This provides O(1) access/insertion/deletion when the key is known, but say the key isn't known and you need to get the key (or a list of keys) from a field eg. from the supplier.

Do current databases just do a linear search with O(n) to return this list?
or do they maintain a list for each field, the keys sorted in order in relation to the field?

twobitadder

ASKER

The list would mean they could get O(1) retrieval of the key.
I'm wanting to connect the theory to the implementation :)

twobitadder

ASKER

>> The list would mean they could get O(1) retrieval of the key.

should be:
a hashed table of entries (hashed from the field, eg. supplier) would allow O(1) retrieval of the keys.

ASKER CERTIFIED SOLUTION

chanito

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

chanito

Forgot to mention... if you create a lot of indexes your inserts will be considerably slowed. This is because every time you insert a record, it needs to insert one in every index table as well. Furthermore, the whole table has to be rearranged to place the new record in the correct position. If you create a clustered index on the main table, then this is also true of the main table. A clustered index means the data is physically ordered in that sequence. This makes searches on that key much faster.

This is why it's not uncommon to disable the creation of statistics in SQL Server for example, because it might hinder your performance quite a bit.

twobitadder

ASKER

Thanks, I'm planning on coding some kind of database as a small project, just wanted to get an idea of what commercial databases do when the key's aren't available :). Profiling sounds a decent option but I think with modern memory capacity I might go for building multiple sorted lists, one list for each field which is paired to its key.