這篇文章不是數(shù)據(jù)庫索引的使用文檔，不會給每個功能的使用都做介紹，而是通過我自己的案例，對案例中遇到的幾個點(diǎn)做詳細(xì)的說明。如果想查看具體的使用幫助，可以參考官網(wǎng)的文檔：Query Planning
“老譚，測試發(fā)現(xiàn)睡眠歷史記錄頁面的打開速度太慢了，你給快速解決一下唄，明天發(fā)版?！?/p>
嗯，所以我還可以換一個標(biāo)題：“如何在1天之內(nèi)將頁面加載性能提升10倍以上”。。行了不廢話，給大家講講這個故事。
太長不看版
- 數(shù)據(jù)庫存儲順序隨機(jī)，如果沒有索引，每次查詢都需要一行行遍歷，查找出符合條件的點(diǎn)，復(fù)雜度 O(N)
- 數(shù)據(jù)庫會按照 rowid 排序，并給主鍵建立索引，所以如果以 rowid 或者主鍵為搜索條件，復(fù)雜度可以近似看做二分查找的復(fù)雜度，即 O(logN)
- 如果沒有主鍵，或搜索條件不是主鍵，可以給搜索目標(biāo)增加索引，將該字段的搜索復(fù)雜度，提升到 O(logN)
- 如果搜索條件有多個，可以建立組合索引 (multi-column index)，將搜索復(fù)雜度，降低到 O(k * logN)
- 注意，如果搜索條件中帶有范圍的搜索，可能導(dǎo)致索引失效，退化到 O(N) 復(fù)雜度，可以通過合理排列聯(lián)合索引的字段順序來避免。
好了，如果這個精簡版看得不過癮，那就請繼續(xù)閱讀，我會用一個案例，也就是本次性能優(yōu)化的故事，來解釋上面的幾點(diǎn)。
問題背景
首先，我們需要先來了解一下我們睡眠應(yīng)用的數(shù)據(jù)設(shè)計(jì)，讓大家對問題域有個基本的了解。
睡眠采用了類似?Google Fit API?的設(shè)計(jì)，將睡眠分為?DataSession?和?DataPoint?兩部分。session 主要用于記錄一次睡眠的開始和結(jié)束時間，而 point 則是所有數(shù)據(jù)的存儲結(jié)構(gòu)。睡眠深度、心率等數(shù)據(jù)，都是以 point 的形式存儲在一張大表中。如果需要展現(xiàn)一次睡眠的記錄，需要首先查找出 session，之后根據(jù) session 的起止時間，找出這個區(qū)間的所有 point。
下面我們簡化一下這個問題，假設(shè) DataPoint 有下面的結(jié)構(gòu)：
class DataPoint {
int type;
long time;
String values;
String account;
}
它確定了數(shù)據(jù)的類型、數(shù)據(jù)發(fā)送的時間，數(shù)據(jù)的值，以及所屬賬號。
每個 point 都是獨(dú)立的，可能被任何 session 包含，所以也有著獨(dú)立的數(shù)據(jù)同步邏輯。如需加載一段睡眠，那么需要將這段睡眠時間內(nèi)所有的 point 都加載出來。在用戶打開歷史記錄頁面時，這個加載過程大致分為這么幾步：
- 從數(shù)據(jù)庫查找當(dāng)前頁面時間范圍內(nèi)的 point，更新到UI。
- 向服務(wù)器請求這段時間的數(shù)據(jù)，用于更新本地的數(shù)據(jù)。
- 從服務(wù)器拉下一串 point 后，更新數(shù)據(jù)庫。如果 point 不存在，則插入該點(diǎn)，如果已經(jīng)存在，則跳過。
- 再次更新UI。
睡眠歷史每次展現(xiàn)一個月，加上預(yù)加載的一個月，需要一次加載兩個月的數(shù)據(jù)。假設(shè)每天有一段8小時的睡眠，每10分鐘有一個睡眠深度數(shù)據(jù)，那么就需要一次加載近3000個數(shù)據(jù)點(diǎn)。
感官上認(rèn)為，這個速度肯定會很慢，但是具體慢在哪里，心里還沒底。于是利用 Android Studio 的?Android Profiler?工具，對加載過程做了分析。最終發(fā)現(xiàn)占用絕大部分時間的，就是數(shù)據(jù)庫的查詢操作。
這是因?yàn)椋趶姆?wù)器拉下更新的 points 后，需要更新數(shù)據(jù)庫。由于需要避免重復(fù)數(shù)據(jù)的插入，所以在每個點(diǎn)的插入前，都需要查找是否有重復(fù)的點(diǎn)。如果與數(shù)據(jù)庫現(xiàn)有點(diǎn)重復(fù)，則需跳過。這就需要大量的查詢的操作，如果說數(shù)據(jù)庫有 M 個點(diǎn)，從服務(wù)器拉下 N 個點(diǎn)，最壞情況，使用遍歷查詢的話，需要做 M x N 次比對，復(fù)雜度是 O(MN)。
那么數(shù)據(jù)庫查詢的復(fù)雜度到底是多少呢？
數(shù)據(jù)庫查詢原理
首先我們需要知道，雖然數(shù)據(jù)庫利用 SQL 語句來構(gòu)建查詢條件，查詢的過程是個黑盒，但它也不是什么魔法，我們可以通過理性分析來估計(jì)其復(fù)雜度。
假設(shè)我們有如下的數(shù)據(jù)表（有一個默認(rèn)的自增長的 rowid）：
| rowid | type | time | values | account |
|---|---|---|---|---|
| 1 | 1 | 10 | ”” | “tankery” |
| 2 | 2 | 10 | ”” | “tankery” |
| 3 | 1 | 50 | ”” | “l(fā)ilya” |
| 4 | 1 | 20 | ”” | “tankery” |
| 5 | 2 | 20 | ”” | “l(fā)ilya” |
可以看到，由于點(diǎn)的插入順序是隨機(jī)的，數(shù)據(jù)點(diǎn)是亂序排列的。那如果我們需要知道一個新的點(diǎn)是否與現(xiàn)有點(diǎn)重復(fù)，需要怎么做呢？由于存儲結(jié)構(gòu)是亂序的，我們只能一個個遍歷。比如我們想知道 {type: 1, time: 20, account: “tankery”} 的點(diǎn)是否與現(xiàn)有數(shù)據(jù)重復(fù)，我們可以構(gòu)建下面的查詢：
SELECT count(*) FROM `data_point`
WHERE `type` = 1
AND `time` = 20
AND `account` = "tankery";
這樣的一個查詢，需要給每一行數(shù)據(jù)都做比較，確定 type, time, account 是否符合條件。其復(fù)雜度是 O(N)。這個性能有多差呢？看看下面這個圖來直觀的感受下：
來源：Jason Feinstein 的博客
也就是說，隨著數(shù)據(jù)量的增大，對排序過的數(shù)據(jù)做二分查找，其時間增長相對 O(N) 來說，幾乎可以忽略不計(jì)了。
那么如何確定數(shù)據(jù)庫的查詢，采用的是什么方法？復(fù)雜度是什么？下面祭出神器，EXPLAIN QUERY PLAN。在查詢語句前加上這句話，讓數(shù)據(jù)庫給你解釋清楚它的查詢計(jì)劃。讓你清清楚楚建索引，明明白白做查詢。那么我們就用這個神器來看看，沒加索引的數(shù)據(jù)庫，采用的是什么方案（我這里使用的是 SQLite 數(shù)據(jù)庫，我猜其他數(shù)據(jù)庫應(yīng)該也會有類似功能）：
EXPLAIN QUERY PLAN
SELECT count(*) FROM `data_point`
WHERE `type` = 1
AND `time` = 20
AND `account` = "tankery";
查詢的結(jié)果是：
| selectid | order | from | detail |
|---|---|---|---|
| 0 | 0 | 0 | SCAN TABLE data_point |
可以看到，沒有增加索引的數(shù)據(jù)庫，確實(shí)是只能使用遍歷 (SCAN) 的方式來一行一行比對了。那么，是時候談?wù)勊饕恕?/p>
數(shù)據(jù)庫索引
索引，就是給某個字段建立了一個排序表，就像是圖書館按照圖書的編號進(jìn)行排序，查找某個編號的圖書時，只需要使用類似二分查找的方式，就可以迅速找到對應(yīng)的圖書了。
數(shù)據(jù)庫會分配一個額外的空間，用來存儲索引表，每次對數(shù)據(jù)庫的修改（插入、修改、刪除），也都會對應(yīng)的修改索引表，所以增加索引以后，會一定程度的增加數(shù)據(jù)庫大小，和數(shù)據(jù)庫修改的時間。因此，如果你的數(shù)據(jù)庫是修改多，查詢少，那么就需要三思一下，增加索引是否有必要了。
對于上面的數(shù)據(jù)表，我們可以用下面的語句對 type 建索引：
CREATE INDEX IF NOT EXISTS "point_type" ON `data_point`(type);
這行SQL語句為 data_point 數(shù)據(jù)表的 type 字段建立了一個名為 point_type 的索引。建立以后，索引表將會以類似下面這樣的形式組織：
| type | rowid |
|---|---|
| 1 | 1 |
| 1 | 3 |
| 1 | 4 |
| 2 | 2 |
| 2 | 5 |
可以看到，索引表按照 type 進(jìn)行了排序，這樣，當(dāng)我們應(yīng)用查詢語句時，數(shù)據(jù)庫能夠非常迅速的在索引表中找到符合條件的 type，并通過對應(yīng)的 rowid，找到原數(shù)據(jù)表中所有值。使用?EXPLAIN QUERY PLAN?來驗(yàn)證一下我們的想法：
| selectid | order | from | detail |
|---|---|---|---|
| 0 | 0 | 0 | SEARCH TABLE data_point USING INDEX point_type (type=?) |
數(shù)據(jù)庫誠不欺我，真的使用了 INDEX 來 SEARCH，而不是 SCAN 了。但是，聰明的你是否發(fā)現(xiàn)，這個索引對于我們的查詢并沒有什么用，迅速查到 type = 1 的數(shù)據(jù)，然后呢？除 type 之外的內(nèi)容沒有排序，還是有一大半的數(shù)據(jù)需要一個個查詢。
這時我們會想，既然索引能加快目標(biāo)字段的查詢速度，那既然我們的查詢需要依賴多個字段，那給每個字段都給建立個索引不就行了？不錯，來試試：
CREATE INDEX IF NOT EXISTS "point_type" ON `data_point`(type);
CREATE INDEX IF NOT EXISTS "point_time" ON `data_point`(time);
CREATE INDEX IF NOT EXISTS "point_account" ON `data_point`(account);
然后再次使用?EXPLAIN QUERY PLAN?來驗(yàn)證我們的想法：
| selectid | order | from | detail |
|---|---|---|---|
| 0 | 0 | 0 | SEARCH TABLE data_point USING INDEX point_type (type=?) |
瘋了瘋了，已經(jīng)為每個字段都加上了索引，這個數(shù)據(jù)庫怎么不聽話，還是只用 type？？“這屆數(shù)據(jù)庫不行”。
但冷靜下來想想，為每個字段單獨(dú)建立索引，就會建立三個依照不同字段進(jìn)行排序的獨(dú)立的索引表，當(dāng)我們使用 type 來索引，這些行對應(yīng)到其他兩個表，就是亂序的，無法二分查找。
這時我們會想，不是還有個組合索引么，可以用它么？
組合索引 (multi-column index)
我們先丟掉之前創(chuàng)建的那些沒用的東西：
DROP INDEX IF EXISTS `point_type`;
DROP INDEX IF EXISTS `point_time`;
DROP INDEX IF EXISTS `point_account`;
然后可以用下面的語句來創(chuàng)建一個組合索引：
CREATE INDEX IF NOT EXISTS "point_query" ON `data_point`(type, time, account);
這是什么意思呢？其實(shí)，組合索引，會將指定的字段，都放入同一張索引表，并且會按照創(chuàng)建時的順序，對各個字段依次進(jìn)行排序。也就是說，對于上面的索引，數(shù)據(jù)庫會先按照 type 排序，再按照 time，然后是 account。這張索引表建立起來，是類似下面這個樣子的：
| type | time | account | rowid |
|---|---|---|---|
| 1 | 10 | “tankery” | 1 |
| 1 | 20 | “tankery” | 4 |
| 1 | 50 | “l(fā)ilya” | 3 |
| 2 | 10 | “tankery” | 2 |
| 2 | 20 | “l(fā)ilya” | 5 |
可以看到，首先是按照 type 排序，如果 type 相等，就按照 time 排序，如果 time 也相等，才會按照 account 排序。看起來不錯，我們再用?EXPLAIN QUERY PLAN?驗(yàn)證一下：
| selectid | order | from | detail |
|---|---|---|---|
| 0 | 0 | 0 | SEARCH TABLE data_point USING COVERING INDEX point_query (type=? AND time=? AND account=?) |
非常棒！將三個查詢條件全都囊括了，而且，原來的 “USING INDEX” 變成了 “USING COVERING INDEX”，什么意思呢？好事壞事？
其實(shí) COVERING INDEX 指的是，索引表已經(jīng)包含了所有查詢所需的信息，無需再通過 rowid 到原始數(shù)據(jù)表中去查找原始數(shù)據(jù)行了。上面這個例子，由于索引表已經(jīng)包含了所有查詢條件，而且我們僅需要 count，不需要具體信息，因此僅僅查詢索引表就已經(jīng)可以獲取到我們所需的查詢結(jié)果。這使得查詢速度又提升了一倍（不需要通過rowid進(jìn)行二次查找）。
看起來非常完美了，打完收工？
范圍查詢 (RANGE SCAN)
范圍查詢實(shí)際上是個比較復(fù)雜的用法了，大部分講數(shù)據(jù)庫索引的文章都不會做介紹，但沒辦法，很多時候我們就是需要做范圍查詢。比如回到我們的問題域。有一個需求是需要加載一個月中所有的數(shù)據(jù)點(diǎn)，也就是數(shù)據(jù)點(diǎn)的 time 字段在某個時間范圍內(nèi)的所有數(shù)據(jù)點(diǎn)，這時，還能不能優(yōu)雅的使用索引來查詢呢？
如果我們?nèi)匀皇褂们拔牡慕M合索引，那么還是使用?EXPLAIN QUERY PLAN?來查看數(shù)據(jù)庫的查詢策略：
EXPLAIN QUERY PLAN
SELECT * FROM `data_point`
WHERE `type` = 1
AND `time` >= 20
AND `time` < 100
AND `account` = "tankery";
結(jié)果如下：
| selectid | order | from | detail |
|---|---|---|---|
| 0 | 0 | 0 | SEARCH TABLE data_point USING INDEX point_query (type=? AND time>? AND time<?) |
為何 account 的索引沒有用上？
回到組合索引的實(shí)現(xiàn)，我們發(fā)現(xiàn)，當(dāng)我們的查詢中包含了一個范圍查詢以后，由于 time 的值是在一個范圍內(nèi)，而不是特定的值時，account 字段就是亂序的了，因?yàn)?account 只有在 time 一致時，才會排序。也就是說，如果需要用上某個字段的索引，那么就必須確保這個字段的前序字段，都是確定的值。
這就引出了建立索引時一個非常重要的原則：“相等查詢的字段，盡量放在組合索引的前面”。
對于我們的業(yè)務(wù)需求，你會發(fā)現(xiàn)，我們還是有機(jī)會用上所有字段的索引，因?yàn)?account 字段，實(shí)際上也是相等查詢。我們按照這個原則，重新創(chuàng)建索引：
DROP INDEX IF EXISTS `point_query`;
CREATE INDEX IF NOT EXISTS "point_query" ON `data_point`(type, account, time);
這個索引建立以后，索引表大概是這個樣子：
| type | account | time | rowid |
|---|---|---|---|
| 1 | “l(fā)ilya” | 50 | 3 |
| 1 | “tankery” | 10 | 1 |
| 1 | “tankery” | 20 | 4 |
| 2 | “l(fā)ilya” | 20 | 5 |
| 2 | “tankery” | 10 | 2 |
也就是按照 type -> account -> time 的順序進(jìn)行排序了。我們分析一下查詢策略，結(jié)果如下：
| selectid | order | from | detail |
|---|---|---|---|
| 0 | 0 | 0 | SEARCH TABLE data_point USING INDEX point_query (type=? AND account=? AND time>? AND time<?) |
終于，我們再次用上了所有的索引字段。
實(shí)測發(fā)現(xiàn)，所有的數(shù)據(jù)庫操作，時間都降到了1s以下，對于一個異步加載，我已經(jīng)心滿意足了。
參考資料
如果你覺得我的故事不好聽，或者想了解更多，可以看看下面幾篇為你精選的文章，祝好。文章來源：http://www.zghlxwxcb.cn/news/detail-774428.html
- Jason Feinstein:?Squeezing Performance from SQLite: Indexes? Indexes!
- SQLite Org:?Query Planning
- Range Query:?Using the Index, Luke
written by: Tankery Chen文章來源地址http://www.zghlxwxcb.cn/news/detail-774428.html
到了這里，關(guān)于為什么要給數(shù)據(jù)庫加索引？轉(zhuǎn)自 https: //blog.tankery.me/development/why-we-need-indexes-for-database的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
