# index 索引

###### tags: `mysql`

## index 原理
- index分類
- 二元樹
- hash index

## hash index
時間複雜度: O(1)
最常見的 innodb 不支援 hash index, 主要原因:
- hash index 適合`精確`查詢, 範圍查詢就不適合
> [mysql hash index & adaptive hash index](https://www.modb.pro/db/113573)

## 二元樹 (binary tree)
- 時間複雜度 O(n)
- 一個節點只能有兩個子節點
- 左邊節點小於本節點, 右邊節點大於本節點

### 平衡二元樹
- 根節點會隨著數據改變
- 數據越多, 遍歷次數越多, IO時間越長

## B tree (二三樹)
point: 儲存child的 address
data: save value

當數據大時，會導致Btree很深，增加IO的讀取次數，影響查詢效率

## B+ Tree
我們也可說他是一顆二元樹，MYSQL index最小單位為 `page`
當要查詢一筆數據時，會先從root page 開始尋找，page 內放 兩個 index key 例如設定id
根據id值往下搜尋page內的數據

- 每一個節點都帶有下一個節點的point
- 所有查詢最後都會到 page 去查詢結果

## 稀疏索引 & 密集索引
Dense: 密集
Sparse: 稀疏

## 二級索引
Secondary Indexes: 二級索引

## Binary Tree 與 B+Tree差異
- B+樹從下而上插入
-
---

## mysql
data page 為最小單位

- file.frm: 表結構
- file.ibd: index and data

## 回表查詢
使用聚集索引可以直接查詢到指針內的數據, 如果是普通索引就需要掃描兩遍 index tree, 先透過 index 找到 PK, 再透過 cluster index 定位數據, 這就是 `回表查詢`

### why不能建太多index
建立一個index時，都是去實作一顆btree，這也是為什麼 不能建立太多index, index也會占用空間

---

## 索引使用場景

### 適合使用索引
- 頻繁作為查詢條件的字段應該創建索引
- 多表查詢中與其它表進行關聯的字段,外鍵關係建立索引
- 單列索引/複合索引的選擇,高併發下傾向於創建複合索引
- 查詢中經常用來排序的字段
- 查詢中經常用來統計或者分組字段

### 不適合使用索引
- 頻繁更新的字段: 每次更新都會影響索引樹
- where條件查詢中用不到的字段
- 表記錄太少
- 經常增刪改的表: 更新了表,索引也得更新才行
- 注意: 如果一張表中,重複的記錄非常多,為它建立索引就沒有太大意義

## 參考資料

> [MYSQL 索引參考](https://juejin.cn/post/6931901822231642125)
>