What is Indexing?

Indexing is used for fast reterival/access/delete from database. Original table is stored in heap(Pages. not Balanced BTree). Index is a seperate datastructure from original table
Each index is stored in seperate file. indexing file contains (key, value=pointer to data in table(called TID(Tuple ID)))

Usage of Indexing
1. if BTree index is created, search complexity will reduce from O(n) or O(logn).
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);

index_file    //Seperate index file
    Key(tenant_name)       Value(pointer_to_row)
          xyz               0x8128129
Searching using index

$ select from tenants where tenant_name=xyz;

Postgres finds idx_tenant_name matches on tenants and tenant_name.
It goes index file, finds key and corresponding data.
if you want efficient search on tenant_id, you have to create a seperate index

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(logn) 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)