https://www.bilibili.com/video/BV1Kr4y1i7ru?p=87&spm_id_from=pageDriver&vd_source=f726dd30598fe01d9fbc9c5a988d6408
必看

bytebytego
https://blog.bytebytego.com/p/database-indexing-strategies

## nosql 索引
https://www.youtube.com/watch?v=I6jB0nM9SKU&ab_channel=ByteByteGo

https://blog.bytebytego.com/p/database-indexing-strategies-part


在寫入 db的部分會先排序在insert

這邊是按照Cassandra去說明的 但基本上LSM tree都是這樣
當memtable達到零界區會刷新到sstable

刪除
會有大量舊數據 查詢時間會變長
所以他為了解決這問題 用下面方法merge 記住因為他是順序的 所以才能這樣
這也是為什麼他被叫做tree的原因

在壓縮方式上

查詢方式


https://wiesen.github.io/post/leveldb-storage-memtable/
# mysql 索引

## order by
https://www.cnblogs.com/qdhxhz/p/16944971.html

## 介紹
索引可分為主索引鍵( primary key )、唯一索引( unique index )與非唯一索引( non-unique index )、 全文檢索( full-text search)

1. 主索引鍵最為常見，而且一個表格通常會有一個，而且只能有一個。在一個表格中，設定為主索引鍵的欄位值不可以重複，而且不可以儲存「NULL」值。適合使用在類似編碼、代號或身份證字號這類欄位。
1. 唯一索引也稱為「不可重複索引」，在一個表格中，設定為唯一索引的欄位值不可以重複，但是可以儲存「NULL」值。
1. 非唯一索引就只是用來增加查詢與維護資料效率的索引。設定為非唯一索引的欄位值可以重複，也可以儲存「NULL」值。
1. 全文檢索則是只能用在「 CHAR 」、「 VARCHAR 」與「 TEXT 」型態的欄位字元型態且允許 「NULL」的欄位所組成。

## 二叉樹
左小右大的特性

子節點只能有兩個, 大數據情況下會有deep問題, 速度最壞會到O(n)
所以要用紅黑數確保再最壞的情況下O(logn)

平衡二叉樹（紅黑數）


為了解決deep問題 但是衍生出大量情況會很慢 因為還算是二叉樹

demo
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
## b-Tree

## B+ 目前的
上面節點是用來index
下面才是存資料 他們也是linked list


頁 上面不存放數據 能放的就變多
而且like list優化成雙向變表 方便範圍查找

## hash index

## 複合索引

單一索引如同上述所說的，然而有時候我們在下WHERE條件，往往不會只只有一個欄位的判定，會搭配著好幾個欄位一併做搜尋排序，這時候使用複合索引就會比單一索引有效率的多，如果都只建立單一索引，MySQL會自動使用他認為最有效率的索引來使用，語法如下：

CREATE INDEX email_tel_index ON member(email, tel);
ALTER TABLE member ADD INDEX email_tel_index (email, tel);

另外在建立複合索引時要仔細考慮索引的先後順序， 如果第一個欄位的選擇性過低或是查詢類型不符，那麼其實該索引對查詢效能就沒什麼明顯幫助，假設建立兩個索引 `index_1 (sex, name, age) 跟 index_2 (name, age, sex)`，在 index_1 中可以發現最左(最先)判斷的性別，但性別包含過多的資料，導致搜尋出來的結果還是很多，並無太大幫助，所以最左邊的應該放置更有識別性的欄位，像是 `index_2的 name` 較具有唯一性，才能大大提升搜尋的效率。
複合索引還有另一個優點，他通過最左前綴`( Leftmost Prefixing )`的概念，顧名思義就是以最左邊的條件為優先，假設用 index_2 為例，當今天使用搜尋時，一共包含了三種搜尋的組合，

name, age, sex
name, age
name

但是不支援 ( age , sex 或者 sex)這樣的組合，簡單來說創建 index (A,B,C)，相當於創建一個單一索引 A 和兩個複合索引 A+B 與 A+B+C (不包括 B+C, C)，所以在考慮建立複合索引時，要把常用或高頻率第一個做檢查的欄位放在索引中的最左邊，可以有效增加搜尋的速度，也可省去再建立重複單一索引值的空間。

## 建立索引時需要考慮的原則

最常見在「WHERE」子句中判斷條件的欄位，還有「 ORDER BY 」與「 GROUP BY 」中指定的欄位，也都可以使用建立索引來增加效率。不過建立這樣的索引的前提，表格所儲存的資料量要夠大，如果量不大的話，建立索引反而會浪費儲存的空間，效率也增加不多，而且還會讓執行新增或修改時的效率變差。

1. 選擇唯一性索引: 唯一性索引的值是唯一的，可以更快速的透過該索引來ˊ找尋資料。
1. 經常需要排序、分組和操作的欄位建立索引: 排序會浪費很多時間。如果建立索引，可以有效地避免排序操作。
1. 索引不要建立過多: 索引的數目不是越多越好。每個索引都需要佔用空間，索引越多，需要的空間就越大。
1. 索引的欄位儘量不要有「NULL」值
1. 最左前綴匹配原則: 最具識別性的欄位放在鍵的左邊
1. 雖然某個欄位很常使用在 WHERE、 ORDER BY 或 GROUP BY 子句中，也不一定要建立索引。例如性別欄位的值只有兩種(F , M)，建立索引所增加的效率也不多
1. 如果有 or，where 後面就必須全部條件有 index，否則 index 將不會起作用，所以要使用 or 的就要為相對應的欄位加上 index

## 索引不會包含有NULL的列

只要列中包含有NULL值，都將不會被包含在索引中，複合索引中只要有一列含有NULL值，那麼這一列對於此符合索引就是無效的。
## 使用短索引

對串列進行索引，如果可以就應該指定一個字首長度。例如，如果有一個char（255）的列，如果在前10個或20個字元內，多數值是唯一的，那麼就不要對整個列進行索引。短索引不僅可以提高查詢速度而且可以節省磁碟空間和I/O操作。

## mysql一張表查詢只能用到一個索引。
因此如果where子句中已經使用了索引的話，那麼order by中的列是不會使用索引的。因此資料庫預設排序可以符合要求的情況下不要使用排序操作，儘量不要包含多個列的排序，如果需要最好給這些列建複合索引。

這一點是很多程式猿容易忽略的，如where子句的欄位建了索引，排序的欄位建了索引，但是分開建的，以為會走索引，其實這樣的話排序的欄位不會使用索引的，除非建複合索引，切記。

## like語句操作

一般情況下不鼓勵使用like操作，如果非使用不可，注意正確的使用方式。 like ‘%aaa%’不會使用索引，而like ‘aaa%’可以使用索引 。

## 不使用索引情況
不使用NOT IN 、<>、！=操作，但<,<=，=，>,>=,BETWEEN,IN是可以用到索引的。

## 索引要建立在經常進行select操作的欄位上

這是因為，如果這些列很少用到，那麼有無索引並不能明顯改變查詢速度。相反，由於增加了索引，反而降低了系統的維護速度和增大了空間需求。

## 不適合建索引
經常插入、刪除、修改的表

資料重複且分佈平均的表字段 。如一個表有10萬行記錄，其中欄位column1只有A和B兩種值，且每個值的分佈概率大約為50%，那麼對這種表column1欄位建索引一般不會提高資料庫的查詢速度

18.給表建立主鍵，對於沒有主鍵的表，在查詢和索引定義上有一定的影響。

19. 避免表字段為null，建議設定預設值（如int型別設定預設值為0），這樣在索引查詢上，效率會高很多。

20.關於 order by 的索引問題重點說下

20.1 無條件查詢如果只有order by create_time，即便create_time上有索引，也不會使用到。
因為優化器認為走二級索引再去回表成本比全表掃描排序更高，所以選擇走全表掃描。
20.2 無條件查詢但是order by create_time limit m，如果m值較小，是可以走索引的。
因為優化器認為根據索引有序性去回表查資料，然後得到m條資料，就可以終止迴圈， 那麼成本比全表掃描小，則選擇走二級索引。 即便沒有二級索引，mysql針對order by limit也做了優化，採用堆排序。

20.3 order by排序分為file sort和index，index的效率更高 。但以下情況不會使用index排序：
20.3.1 檢查的行數過多，並且沒有使用覆蓋索引
20.3.2 使用了多個索引，mysql一次只會採用一個索引（切記）

20.3.3 where和order by使用了不同的索引，與上一條類似
20.3.4 order by中加入了非索引列，且非索引列不在where中
20.3.5 當使用left join，使用右邊的表字段排序

###### tags: `MySql`