數據庫索引通常由一組索引鍵（或索引字段）構成，這些鍵的值被存儲在一個數據結構中，以便快速查找特定的行。
數據庫索引是一種用于加快數據庫查詢速度的數據結構，它類似于書籍的目錄，可以幫助快速定位到表中某個或某些特定的行。數據庫索引通常由一組索引鍵（或索引字段）構成，這些鍵的值被存儲在一個數據結構中，以便快速查找特定的行。
索引的類型（實現方式）
數據庫索引有多種分類方法，從索引的實現方式常見的有：
- B+樹索引
- 哈希索引
- 空間索引（例如 R-樹）
- 全文索引
- Bitmap索引
每種索引類型適用于不同的數據類型和查詢類型，應根據具體需求選擇合適的索引類型。
B+樹索引
B+樹是一種平衡樹，每個節點包含一定數量的關鍵字和指向子節點的指針，以支持快速的查詢和排序。B+樹索引適用于各種數據類型，并且支持范圍查詢和排序，因此在許多數據庫系統中廣泛使用。
B+樹索引示意圖
注: 圖片來源自Wikipedia(https://zh.wikipedia.org/wiki/File:Bplustree.png)
當數據庫執行查詢時，它首先在B-樹索引中搜索包含查詢所需關鍵字的節點，然后通過指針找到包含該關鍵字的數據記錄。如果查詢是范圍查詢，則B-樹索引還可以通過查詢包含范圍內關鍵字的節點，并返回所有符合條件的數據記錄。
B+樹索引的優點
- 支持快速的查詢和排序，提高數據庫的性能。
- 支持各種數據類型，可以索引數值型，字符串型和日期/時間型數據。
- 可以處理大量的數據，因為它是一種平衡樹。
B+樹索引的缺點
- 在插入或刪除數據時，B+樹可能需要重新平衡，以維護平衡樹的性質，因此插入或刪除操作可能會變慢。
- 在更新數據時，需要刪除原來的數據記錄并創建新的數據記錄，因此可能會消耗大量的時間和空間。
Hash索引
Hash索引是一種基于哈希表的索引，它使用哈希函數將數據映射到哈希表中的桶（bucket）。
Hash索引示意圖
注: 圖片來源自Wikipedia(https://en.wikipedia.org/wiki/Hash_table)
當數據庫執行查詢時，它使用哈希函數計算查詢所需關鍵字的哈希值，然后在哈希表中查找具有相同哈希值的數據記錄。如果發現多個數據記錄具有相同的哈希值，則必須使用比較運算符來確定實際的數據記錄。
Hash索引的優點
- 在查詢數據時非常快，因為可以直接訪問桶。
- 對于等值查詢特別有效，因為可以直接定位需要的數據。
- 無需進行排序，因此無需消耗額外的時間和空間。
Hash索引的缺點
- 不支持范圍查詢和排序。
- 哈希沖突可能導致查詢變慢，因為必須使用比較運算符進一步檢查數據記錄是否匹配。
- 不適用于所有數據類型，僅適用于數值型數據。
- 插入，更新和刪除操作可能需要重新散列，以維護哈希表的性質。
空間索引
空間索引是一種專門用于處理空間數據的索引，通常用于地理信息系統（GIS）和空間數據庫中。它是用于快速查詢空間數據的位置和幾何關系的索引。
R-Tree示意圖
注: 圖片來源自Wikipedia
空間索引通常使用網格結構，如格網、網格圖或四叉樹，將空間數據劃分為許多小的網格單元。每個網格單元存儲其中的一個或多個數據點，并使用空間算法快速查詢其他網格單元，以確定數據點的幾何關系。
空間索引的優點
- 可以快速查詢空間數據的位置和幾何關系。
- 對于查詢空間數據的范圍，如矩形范圍、圓形范圍等，非常有效。
- 用于快速查詢數據的投影和視圖。
空間索引的缺點
- 比較復雜，需要許多空間算法的知識。
- 不適用于非空間數據。
- 當數據數量很大時，可能需要大量內存。
全文索引
全文索引是用于快速搜索文本內容的索引。它可以在數據庫中搜索文本字段，或者在文檔管理系統中搜索文件內容。全文索引通常通過對文本內容進行分詞（將文本分解為單詞），并使用數據結構（如倒排索引）存儲分詞后的信息，以便快速查詢搜索詞。
全文索引的優點
- 可以快速搜索文本內容。
- 可以搜索模糊詞。
- 可以處理多語言文本。
全文索引的缺點
- 對于非文本數據不適用。
- 可能需要大量計算和存儲資源，特別是當文本數據較大時。
- 可能存在誤判或誤識別情況。
位圖索引
Bitmap索引是一種特殊的數據索引，它通過將數據存儲為二進制位映射（Bitmap）來加速查詢。每個位代表一個數據記錄是否符合某個特定條件。例如，如果某個位為1，則表示該記錄符合某個條件，如果為0，則表示該記錄不符合條件。
Bitmap索引的優點：
- 高效。Bitmap索引可以很快執行大量的邏輯運算，從而提高查詢效率。
- 空間效率。Bitmap索引在存儲數據時非常緊湊，因為它只需要存儲0和1的二進制位。
Bitmap索引的缺點：
- 數據更新困難。當數據更改時，需要重新生成整個Bitmap索引，這可能很耗時。
- 僅適用于特定類型的數據。Bitmap索引僅適用于具有限制類別數量的數據，例如城市或性別等。
因此，Bitmap索引通常適用于具有較少不同值的列，以加速查詢。
其他分類
唯一索引
從唯一性的角度，索引可以分為唯一性索引和非唯一性索引。唯一性索引可以用來保證表中某個列的唯一性約束條件，通常用于實現主鍵約束和唯一性約束，數據庫通常會為主鍵或是唯一性約束自動創建唯一性索引。
唯一性索引優缺點
唯一性索引不僅可以提高查詢的效率，還可以起到數據校驗的作用，避免了重復數據的產生，提高數據的質量和準確性。它的缺點是每當有數據修改或是插入時，需要檢查是否違反唯一性約束。
聚簇索引
從聚簇率的角度，索引可以分為聚簇索引或非聚簇索引。聚簇索引的索引鍵的排列順序和數據表中數據的排列順序一致的索引，每個表只能有一個聚簇索引，因為數據表的數據只能以一種方式進行排序。
在一些比較先進的數據庫優中，對于非聚簇索引也會計算其聚簇率，以方便優化器評估回表時磁盤IO的代價。聚簇率小的索引回表時，會引起磁盤IO的抖動，從而明顯影響查詢性能，一般來講，聚簇率越大，其磁盤IO的代價越小。
聚簇索引有兩種實現方式，
- 一是聚簇索引和表數據存儲在一起，索引樹中的每個葉子節點都存儲一個完整的表行，以MySQL的InnoDB引擎和SQL Server為代表。
- 二是聚簇索引和表的數據是分離的，可以先有表，然后定義聚簇索引，以DB2，PostgreSQL， Oracle為代表。
聚簇索引優缺點
聚簇索引的優勢是可以減少磁盤I/O次數，從而提高查詢性能。但是，聚簇索引也有一些缺點，譬如當插入新數據時，它可能需要移動數據頁或重新組織索引，這可能會對性能產生負面影響。
二級索引
從是否是主鍵的角度，索引可以分為主鍵索引和二級索引，主鍵索引只能有一個，二級索引可以有多個。
組合索引
從包含的索引列的數目的角度，索引可以分為單列索引和組合索引。組合索引可以滿足多種查詢條件，從而節省索引的空間和索引維護的代價。組合索引的匹配原則遵循最左前綴匹配原則，詳細信息請參考《如何創建高效的索引》。
函數索引
函數索引（或表達式索引）即基于函數或表達式的索引，它使用函數或是表達式提供計算好的值作為索引列構建索引，可以在不修改應用程序的情況下提高查詢性能。案例如下：
alter table lineitem add index idx(DAYOFMONTH(l_shipdate));
DAYOFMONTH是PostgreSQL自帶的函數，它從日期中獲取天。
條件索引
部分索引(Partial index)是建立在一個表的子集上的索引，而該子集是由一個條件表達式定義的，該索引只包含表中那些滿足這個條件表達式的行。案例如下：
create index l_partkey_idx on lineitem(l_partkey) where l_shipdate > '2022-01-01';
總結
- B+樹索引：B+樹索引是最常用的索引類型，具有平衡樹的性質，可以有效的維護大量的數據，適用于大部分數據類型，特別是數值型和字符串型數據，并且支持區間查詢;由于B樹索引的有序性，使用B-樹索引可以節省SQL查詢中所需的排序操作。
- 哈希索引：哈希索引是基于哈希表的索引類型，適用于精確匹配查詢，查詢效率高，但不支持范圍查詢和排序操作。
- 空間索引：空間索引是一種用于空間數據的索引，用于處理空間數據的查詢和管理，譬如R-樹。
- 全文索引：全文索引是用于文本數據的索引類型，主要用于文本搜索和排名。
- Bitmap索引：Bitmap索引是一種特殊的索引類型，使用位圖來維護索引，適用于處理大量布爾數據的查詢。
