The cost of indexing in database

content

indexing is creating a data structure (a tree) based on the record in the existing table
so whenever the existing table has a change in records (update, delete, insert), the index data structure has to be refreshed
it’s important to evaluate the cost-benefit of creating an index (B Tree):
- without indexing
  - insertion is constant time O(1) (it’s just inserting to the end of the table)
  - read is linear time O(n) (every single record has to be gone through)
- with indexing
  - insertion is logarithmic time O(log n) (it has to maintain the tree now)
  - read is also logarithmic time O(log n) (it’s reading the tree now)