What is Indexing?

Indexing is used for fast reterival/access/delete from database. Create a seperate datastructure from original

Usage of Indexing
1. if BTree index is created, search complexity will reduce from O(n) or O(nlogn).
2. if Hash index is created, search complexity will reduce from O(n) or O(1).

Example:
  1. consider 100M entries in tenants table
  2. If we donot create index, and someone searches tenant_name then it will take O(n) time to search entry 

// 2. tenants table
| id | tenant_name |
| 1  | abc |
| 2  | xyz |
...

// 2. Searching in tenants table
> SELECT id FROM tenants WHERE tenant_name = 'abc';
Creating Btree index on Tenants Table

CREATE UNIQUE INDEX idx_tenant_name ON tenants(tenant_name);
What is meaning of Creating index?
When index is created a additional data structure is created typically a B-Tree (or a variant like a B+Tree), that means original data remains in table, a new B-Tree is created from table data

Types of Indexing

Type of Indexing Description Creation
Hash Index Pros:
 Search: O(1)
Cons:
  Does not support Range queries(e.g., WHERE tenant_name > 'tenant1').
  Does not support sorting or ordering 		This creates a B-Tree Index by default in most relational databases (e.g., PostgreSQL, MySQL, Oracle, SQL Server).
B-Tree is the default index type because it is versatile and supports a wide range of query types. 

CREATE UNIQUE INDEX idx_tenant_name ON tenants(tenant_name);
Btree O(nlogn) Pros: Support exact match queries(WHERE tenant_name = 'tenant1'), range queries, and sorting.
Cons: Slightly slower wrt Hash index but still very fast. 		PostgreSQL's Hash Indexes are not crash-safe in older versions (pre-10.0), so they were discouraged.
However, in modern versions, they are crash-safe and can be used. 

CREATE INDEX idx_tenant_name_hash ON tenants USING HASH (tenant_name);
Bitmap Index Used for columns with low cardinality (few distinct values, e.g., gender or status flags).
R-Tree Used for spatial data (e.g., geographic coordinates).
Full-Text Index Used for searching text data (e.g., WHERE description LIKE '%keyword%').

Reverse Indexing

Reverse indexing is used for efficient reverse lookups.
See Indexing.
Reverse Indexing is reverse mapping. <key=user's node address, value=user_id's>, it will help to map all userId's associated with a particular address.

Reverse Hash Table: 

(Key: user_address, Value: List of user_ids associated with that address)

When Reverse Lookup is useful

when we need to perform lookups based on attributes other than the primary key (user ID)