整合營(yíng)銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
者 | Amazing10
責(zé)編 | 屠敏
頭圖 | CSDN 下載自視覺(jué)中國(guó)
本文為「業(yè)余碼農(nóng)」投稿
索引的概念基本所有人都會(huì)遇到過(guò)，就算沒(méi)有了解過(guò)數(shù)據(jù)庫(kù)中的索引，在生活中也不可避免的接觸到。比方說(shuō)書(shū)籍的目錄，字典的查詢頁(yè)，圖書(shū)館的科目檢索等等。其實(shí)這些都是一種索引，并且所起到的作用大同小異。
而對(duì)于數(shù)據(jù)庫(kù)而言，只不過(guò)是將索引的概念抽象出來(lái)，讓建立索引的過(guò)程更為靈活而自由，從而可以在不同的場(chǎng)景下優(yōu)化數(shù)據(jù)庫(kù)的查詢效率。
索引在數(shù)據(jù)庫(kù)的實(shí)際應(yīng)用場(chǎng)景中十分普遍，數(shù)據(jù)庫(kù)的優(yōu)化也離不開(kāi)對(duì)索引的優(yōu)化。同時(shí)，索引相關(guān)的知識(shí)也是面試高頻的考點(diǎn)之一，是應(yīng)試者理論結(jié)合現(xiàn)實(shí)最為直接的體現(xiàn)。
因此，本文將從基礎(chǔ)理論出發(fā)，介紹 MySQL 按照邏輯角度的索引分類和實(shí)現(xiàn)，通過(guò)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)原理闡述不同結(jié)構(gòu)對(duì)建立索引帶來(lái)的優(yōu)劣勢(shì)，同時(shí)針對(duì)物理存儲(chǔ)的方式對(duì)索引的組織特點(diǎn)和應(yīng)用場(chǎng)景進(jìn)行分析。最后根據(jù)不同的應(yīng)用場(chǎng)景盡可能的探究如何建立起高性能的索引。文章結(jié)構(gòu)如下：
概念
索引似乎并沒(méi)有十分明確的定義，更多的是一種定性的描述。簡(jiǎn)單來(lái)講，索引就是一種將數(shù)據(jù)庫(kù)中的記錄按照特殊形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。通過(guò)索引，能夠顯著地提高數(shù)據(jù)查詢的效率，從而提升服務(wù)器的性能。
專業(yè)一點(diǎn)來(lái)說(shuō)呢，索引是一個(gè)排好序的列表，在這個(gè)列表中存儲(chǔ)著索引的值和包含這個(gè)值的數(shù)據(jù)所在行的物理地址。在數(shù)據(jù)庫(kù)十分龐大的時(shí)候，索引可以大大加快查詢的速度，這是因?yàn)槭褂盟饕罂梢圆挥脪呙枞韥?lái)定位某行的數(shù)據(jù)，而是先通過(guò)索引表找到該行數(shù)據(jù)對(duì)應(yīng)的物理地址然后訪問(wèn)相應(yīng)的數(shù)據(jù)。
說(shuō)起索引，其實(shí)并不是 MySQL 數(shù)據(jù)庫(kù)特有的機(jī)制，在關(guān)系型數(shù)據(jù)庫(kù)中都會(huì)有類似不同的實(shí)現(xiàn)。這里我們也只是討論 MySQL 數(shù)據(jù)庫(kù)中的索引實(shí)現(xiàn)。
事實(shí)上，說(shuō)是 MySQL 的索引其實(shí)并不準(zhǔn)確。因?yàn)樵?MySQL 中，索引是在存儲(chǔ)引擎層而不是服務(wù)器層實(shí)現(xiàn)的。這意味著我們所討論的索引準(zhǔn)確來(lái)說(shuō)是 InnoDB 引擎或 MyISAM 引擎或其它存儲(chǔ)引擎所實(shí)現(xiàn)的。
所以索引即便是在 MySQL 中也沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)，不同存儲(chǔ)引擎的所實(shí)現(xiàn)的索引工作方式也并不一樣。不是所有的存儲(chǔ)引擎都支持相同類型的索引，即便是多個(gè)引擎支持同一種類型的索引，其底層的實(shí)現(xiàn)也可能不同。
說(shuō)了這么多，索引似乎就是給數(shù)據(jù)庫(kù)添加了一個(gè)「目錄頁(yè)」，能夠方便查詢數(shù)據(jù)。但是索引的作用就僅此而已了嗎，為什么需要大費(fèi)周章的建立并優(yōu)化索引？
說(shuō)個(gè)題外話，我其實(shí)查字典從來(lái)都不喜歡查目錄頁(yè)，無(wú)論是查中文還是英文。因?yàn)橛X(jué)得那樣很慢，一個(gè)個(gè)找索引，效率很低。我習(xí)慣用的方式就是直接翻開(kāi)字典，根據(jù)翻開(kāi)的位置進(jìn)行前后調(diào)整。比方說(shuō)我想找「醬 JIANG」字，會(huì)先隨機(jī)翻到一頁(yè)，可能是「F」開(kāi)頭，在「J」前面，就往后翻一點(diǎn)；如果隨機(jī)翻到「L」，那就往前翻一點(diǎn)。重復(fù)直至找到。
這大概就是類似于二分查找的方式，看起來(lái)好像是擺脫了索引的束縛，并且也能夠獲得比較高的查詢效率。但是其實(shí)轉(zhuǎn)念一想，在計(jì)算機(jī)的運(yùn)行處理中，「一個(gè)個(gè)找索引」這個(gè)過(guò)程其實(shí)非常快，不能跟我們手動(dòng)比對(duì)偏旁部首的效率相提并論。同時(shí)，為什么我可以直接翻開(kāi)字典根據(jù)字母進(jìn)行調(diào)整呢，這其實(shí)不就是因?yàn)槲业哪X子里存在一個(gè)大概的「索引表」，知道每個(gè)字母大概對(duì)應(yīng)于字典的哪一個(gè)位置。雖然是模糊的，但卻是真實(shí)存在的。（好不容易強(qiáng)行解釋了一波...）
如此一來(lái)，可以看出索引的一大好處是如其概念中所提及的，使用索引后可以不用掃描全表來(lái)定位某行的數(shù)據(jù)，而是先通過(guò)索引表找到該行數(shù)據(jù)對(duì)應(yīng)的物理地址然后訪問(wèn)相應(yīng)的數(shù)據(jù)。這樣的方式自然減少了服務(wù)器在響應(yīng)時(shí)所需要對(duì)數(shù)據(jù)庫(kù)掃描的數(shù)據(jù)量。
不僅如此，在執(zhí)行數(shù)據(jù)庫(kù)的范圍查詢時(shí)，若不使用索引，那么MySQL會(huì)先掃描數(shù)據(jù)庫(kù)的所有行數(shù)據(jù)并從中篩選出目標(biāo)范圍內(nèi)的行記錄，將這些行記錄進(jìn)行排序并生成一張臨時(shí)表，然后通過(guò)臨時(shí)表返回用戶查詢的目標(biāo)行記錄。這個(gè)過(guò)程會(huì)涉及到臨時(shí)表的建立和行記錄的排序，當(dāng)目標(biāo)行記錄較多的時(shí)候，會(huì)大大影響范圍查詢的效率。
所以當(dāng)添加索引時(shí)，由于索引本身具有的順序性，使得在進(jìn)行范圍查詢時(shí)，所篩選出的行記錄已經(jīng)排好序，從而避免了再次排序和需要建立臨時(shí)表的問(wèn)題。
同時(shí)，由于索引底層實(shí)現(xiàn)的有序性，使得在進(jìn)行數(shù)據(jù)查詢時(shí)，能夠避免在磁盤(pán)不同扇區(qū)的隨機(jī)尋址。使用索引后能夠通過(guò)磁盤(pán)預(yù)讀使得在磁盤(pán)上對(duì)數(shù)據(jù)的訪問(wèn)大致呈順序的尋址。這本質(zhì)上是依據(jù)局部性原理所實(shí)現(xiàn)的。
局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。由于磁盤(pán)順序讀取的效率很高(不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間) ，因此對(duì)于具有局部性的程序來(lái)說(shuō)，磁盤(pán)預(yù)讀可以提高I/O效率。
磁盤(pán)預(yù)讀要求每次都會(huì)預(yù)讀的長(zhǎng)度一般為頁(yè)的整數(shù)倍。而且數(shù)據(jù)庫(kù)系統(tǒng)將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁(yè)，這樣每個(gè)節(jié)點(diǎn)只需要一次 I/O 就可以完全載入。這里的頁(yè)是通過(guò)頁(yè)式的內(nèi)存管理所實(shí)現(xiàn)的，概念在這里簡(jiǎn)單提一嘴。
分頁(yè)機(jī)制就是把內(nèi)存地址空間分為若干個(gè)很小的固定大小的頁(yè)，每一頁(yè)的大小由內(nèi)存決定。這樣做是為了從虛擬地址映射到物理地址，提高內(nèi)存和磁盤(pán)的利用率。
所以呢，總結(jié)一下。索引的存在具有很大的優(yōu)勢(shì)，主要表現(xiàn)為以下三點(diǎn)：
索引大大減少了服務(wù)器需要掃描的數(shù)據(jù)量
索引可以幫助服務(wù)器避免排序和臨時(shí)表
索引可以將隨機(jī) I/O 變成順序 I/O
以上三點(diǎn)能夠大大提高數(shù)據(jù)庫(kù)查詢的效率，優(yōu)化服務(wù)器的性能。因此一般來(lái)說(shuō)，為數(shù)據(jù)庫(kù)添加高效的索引對(duì)數(shù)據(jù)庫(kù)進(jìn)行優(yōu)化的重要工作之一。
不過(guò)，凡事都有兩面性。索引的存在能夠帶來(lái)性能的提升，自然在其它方面也會(huì)付出額外的代價(jià)。
索引本身以表的形式存儲(chǔ)，因此會(huì)占用額外的存儲(chǔ)空間；
索引表的創(chuàng)建和維護(hù)需要時(shí)間成本，這個(gè)成本隨著數(shù)據(jù)量增大而增大；
構(gòu)建索引會(huì)降低數(shù)據(jù)的修改操作（刪除，添加，修改）的效率，因?yàn)樵谛薷臄?shù)據(jù)表的同時(shí)還需要修改索引表；
所以對(duì)于非常小的表而言，使用索引的代價(jià)會(huì)大于直接進(jìn)行全表掃描，這時(shí)候就并不一定非得使用索引了。沒(méi)辦法，成年人的世界總是這么的趨利避害。
從邏輯的角度來(lái)對(duì)索引進(jìn)行劃分的話，可以分為單列索引、全文索引、組合索引和空間索引。其中單列索引又可分為主鍵索引、唯一索引和普通索引。這里的邏輯可以理解為從 SQL 語(yǔ)句的角度，或者是從數(shù)據(jù)庫(kù)關(guān)系表的角度。下面就簡(jiǎn)單介紹這些索引的作用和用法，以及在修改表的時(shí)候如何添加索引。
即主索引，根據(jù)主鍵建立索引，不允許重復(fù)，不允許空值；
主鍵：數(shù)據(jù)庫(kù)表中一列或列組合（字段）的值，可唯一標(biāo)識(shí)表中的每一行。
加速查詢 + 列值唯一（不可以有）+ 表中只有一個(gè)
ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col');用來(lái)建立索引的列的值必須是唯一的，允許空值。唯一索引不允許表中任何兩行具有相同的索引值。比方說(shuō)，在 employee 表中職員的姓 name 上創(chuàng)建了唯一索引，那么就表示任何兩個(gè)員工都不能同姓。
加速查詢 + 列值唯一（可以有）
ALTER TABLE 'table_name' ADD UNIQUE index_name('col');用表中的普通列構(gòu)建的索引，沒(méi)有任何限制。
僅加速查詢
ALTER TABLE 'table_name' ADD INDEX index_name('col');用大文本對(duì)象的列構(gòu)建的索引
ALTER TABLE 'table_name' ADD FULLTEXT INDEX ft_index('col');用多個(gè)列組合構(gòu)建的索引，這多個(gè)列中的值不允許有空值。
多列值組成一個(gè)索引，專門(mén)用于組合搜索，其效率大于索引合并。
ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3');在對(duì)多列組合建立索引時(shí)，會(huì)遵循「最左前綴」原則。
最左前綴原則：顧名思義，就是最左優(yōu)先，上例中我們創(chuàng)建了 (col1, col2, col3) 多列索引,相當(dāng)于創(chuàng)建了 (col1) 單列索引，(col1, col2) 組合索引以及 (col1, col2, col3) 組合索引。
所以當(dāng)我們?cè)趧?chuàng)建多列索引時(shí)，要根據(jù)業(yè)務(wù)場(chǎng)景，將 where 子句中使用最頻繁的一列放在最左邊。
對(duì)空間數(shù)據(jù)類型的字段建立的索引，底層可通過(guò) R 樹(shù)實(shí)現(xiàn)。只不過(guò)使用較少，了解即可。
我們知道，索引的底層本身就是通過(guò)數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行實(shí)現(xiàn)的。那么根據(jù)其底層的結(jié)構(gòu)，常見(jiàn)的索引類型可分為哈希索引，BTree 索引，B+Tree 索引等。這里我們就主要來(lái)介紹這三種索引背后的實(shí)現(xiàn)機(jī)制。
顧名思義，哈希索引是通過(guò)哈希表實(shí)現(xiàn)的。哈希表的特點(diǎn)在之前的文章「九大數(shù)據(jù)結(jié)構(gòu)」中已經(jīng)詳細(xì)介紹過(guò)。通過(guò)哈希表的鍵值之間的對(duì)應(yīng)關(guān)系，能夠在查詢時(shí)精確匹配索引的所有列。哈希索引將所有的根據(jù)索引列計(jì)算出來(lái)的哈希碼存儲(chǔ)在索引中，同時(shí)將指向每個(gè)數(shù)據(jù)行的指針保存在哈希表中。
上圖是通過(guò)哈希索引查詢行數(shù)據(jù)的示意圖，可以發(fā)現(xiàn)哈希索引同樣會(huì)發(fā)生哈希沖突，并且是通過(guò)鏈地址法解決沖突的。當(dāng)發(fā)送沖突時(shí)，還需要對(duì)鏈表進(jìn)行遍歷對(duì)比，才能夠找到最終的結(jié)果。
在 MySQL 中，只有 Memory 存儲(chǔ)引擎顯式的支持哈希索引，而innodb是隱式支持哈希索引的。
這里的隱式支持是指，innodb引擎有一個(gè)特殊的功能 “自適應(yīng)哈希索引”，當(dāng)innodb注意到一些索引值被使用的非常頻繁時(shí)，且符合哈希特點(diǎn)（如每次查詢的列都一樣），它會(huì)在內(nèi)存中基于 B-Tree 索引之上再創(chuàng)建一個(gè)哈希索引。這樣就讓 BTree 索引也具有哈希索引的一些有點(diǎn)。這是一個(gè)完全自動(dòng)的、內(nèi)部的行為。
由于哈希結(jié)構(gòu)的特殊性，其用于非常高的檢索效率，通過(guò)哈希函數(shù)的映射可以一步到位。但是同樣也是因?yàn)榻Y(jié)構(gòu)的特殊，導(dǎo)致哈希索引只適用于某些特定的場(chǎng)合。哈希索引的限制[1]：
不支持范圍查詢，比如 WHERE a > 5；只支持等值比較查詢，包括＝、IN 、<=>
無(wú)法被用來(lái)避免數(shù)據(jù)的排序操作；因?yàn)榻?jīng)過(guò)了哈希函數(shù)的映射過(guò)程，使得丟失了哈希前后的大小關(guān)系，從而無(wú)法按照索引值的順序存儲(chǔ)。
不支持部分索引列的匹配查找，因?yàn)楣Ｋ饕冀K使用索引列的全部?jī)?nèi)容來(lái)計(jì)算哈希值。例如在數(shù)據(jù)列 (A, B) 上建立哈希索引，如果查詢只有數(shù)據(jù)列 A，則無(wú)法使用該索引。
無(wú)法避免表掃描。因?yàn)楫?dāng)出現(xiàn)哈希沖突的時(shí)候，存儲(chǔ)引擎必須遍歷鏈表（拉鏈法）中所有的行指針，逐行進(jìn)行比較，直到找到所有符合條件的行。
哈希沖突很多的情況下，其索引維護(hù)的代價(jià)很高，并且性能并不一定會(huì)比 BTree 索引高。
BTree 實(shí)際上是一顆多叉平衡搜索樹(shù)。從名字可以看出，BTree 首先是一顆多叉搜索樹(shù)，這意味著它是具有順序的；其次 BTree 還是平衡的，這意味著它的左右子樹(shù)高度差小于等于1。
事實(shí)上一顆 BTree 需要滿足以下幾個(gè)條件：
每個(gè)葉子結(jié)點(diǎn)的高度都是一樣的；
每個(gè)非葉子結(jié)點(diǎn)由 n-1 個(gè) key 和 n 個(gè)指針 point 組成，其中 d<=n<=2d, key 和 point 相互間隔，結(jié)點(diǎn)兩端一定是 key；
葉子結(jié)點(diǎn)指針都為 ；
非葉子結(jié)點(diǎn)的key都是 [key, data] 二元組，其中 key 表示作為索引的鍵，data 為鍵值所在行的數(shù)據(jù)；
一顆常見(jiàn)的BTree樹(shù)見(jiàn)下圖。
這是一顆三階的BTree，可通過(guò)鍵值的大小排序進(jìn)行數(shù)據(jù)的查詢和檢索，其中葉子節(jié)點(diǎn)的指針都為空，因此省略沒(méi)畫(huà)。從上圖可以發(fā)現(xiàn)，BTree 的樹(shù)形狀相較于我們之前常見(jiàn)的二叉樹(shù)等結(jié)構(gòu)，更為扁平和矮胖。
之所以這樣設(shè)計(jì)，還是跟磁盤(pán)讀取的特點(diǎn)有關(guān)。我們知道在建立索引時(shí)，也是需要占據(jù)物理空間的。而實(shí)際上當(dāng)數(shù)據(jù)量比較大的時(shí)候，索引文件的大小也十分嚇人。考慮到一個(gè)表上可能有多個(gè)索引、組合索引、數(shù)據(jù)行占用更小等情況，索引文件的大小可能達(dá)到物理盤(pán)中數(shù)據(jù)的1/10，甚至可達(dá)到1/3。
這就意味著索引無(wú)法全部裝入內(nèi)存之中。當(dāng)通過(guò)索引對(duì)數(shù)據(jù)進(jìn)行訪問(wèn)時(shí)，不可避免的需要對(duì)磁盤(pán)進(jìn)行讀寫(xiě)訪問(wèn)。同時(shí)我們還知道，內(nèi)存的讀寫(xiě)速度是磁盤(pán)的幾個(gè)數(shù)量級(jí)。因此在對(duì)索引結(jié)構(gòu)進(jìn)行設(shè)計(jì)時(shí)要盡可能的減少對(duì)磁盤(pán)的讀寫(xiě)次數(shù)，也就是所謂的磁盤(pán) I/O 次數(shù)。
這也就是索引會(huì)采用 BTree 這種扁平樹(shù)結(jié)構(gòu)的原因，樹(shù)的層數(shù)越少，磁盤(pán)I/O的次數(shù)自然就越少。不僅如此，我們上面提到過(guò)磁盤(pán)預(yù)讀的局部性原理。根據(jù)這個(gè)原理再加上頁(yè)表機(jī)制，能夠在進(jìn)行磁盤(pán)讀取的時(shí)候更大化的提升性能。
BTree 相較于其它的二叉樹(shù)結(jié)構(gòu)，對(duì)磁盤(pán)的 I/O 次數(shù)已經(jīng)非常少了。但是在實(shí)際的數(shù)據(jù)庫(kù)應(yīng)用中仍有些問(wèn)題無(wú)法解決。
一是無(wú)法定位到數(shù)據(jù)行。通過(guò) BTree 可以根據(jù)主鍵的排序定位出主鍵的位置，但是由于數(shù)據(jù)表的記錄有多個(gè)字段，僅僅定位到主鍵是不夠，還需要定位到數(shù)據(jù)行。雖然這個(gè)問(wèn)題可以通過(guò)在 BTree 的節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)行或者增加定位的字段，但是這種方式會(huì)使得 BTree 的深度大幅度提高，從而也導(dǎo)致 I/O 次數(shù)的提高。
二是無(wú)法處理范圍查詢。在實(shí)際的應(yīng)用中，數(shù)據(jù)庫(kù)范圍查詢的頻率非常高，而 BTree 只能定位到一個(gè)索引位置。雖然可以通過(guò)先后查詢范圍的左右界獲得，但是這樣的操作實(shí)際上無(wú)法很好的利用磁盤(pán)預(yù)讀的局部性原理，先后查詢可能會(huì)造成通過(guò)預(yù)讀取的物理地址離散，使得 I/O 的效率并不高。
三是當(dāng)數(shù)據(jù)量一大時(shí)，BTree的高度依舊會(huì)變得很高，搜索效率還是會(huì)大幅度的下降。
問(wèn)題總是推動(dòng)改進(jìn)的前提。基于以上的問(wèn)題考慮，就出現(xiàn)了對(duì) BTree 的優(yōu)化版本，也就是 B+Tree。
B+Tree 一看就是在 BTree 的基礎(chǔ)上做了改進(jìn)，那么到底改變了什么呢。廢話不多說(shuō)，先上圖。
上圖實(shí)際上是一種帶有順序索引的 B+Tree，與最基本的 B+Tree 的區(qū)別就在于葉子節(jié)點(diǎn)是否通過(guò)指針相連。一般數(shù)據(jù)庫(kù)中常用的結(jié)構(gòu)都是這種帶有順序索引的 B+Tree。后文探討的也都是帶順序索引的 B+Tree 結(jié)構(gòu)。
對(duì)比 BTree 和 B+Tree，我們可以發(fā)現(xiàn)二者主要在以下三個(gè)方面上的不同：
非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息，不再存儲(chǔ)數(shù)據(jù)。
所有葉子節(jié)點(diǎn)之間都有一個(gè)鏈指針，指向下一個(gè)葉子節(jié)點(diǎn)。
數(shù)據(jù)都存放在葉子節(jié)點(diǎn)中。
看著 B+Tree，像不像是一顆樹(shù)與一個(gè)有序鏈表的結(jié)合體。因而其實(shí) B+Tree 也就是帶有樹(shù)和鏈表的部分優(yōu)勢(shì)。樹(shù)結(jié)構(gòu)使得有序檢索更為簡(jiǎn)單，I/O 次數(shù)更少；有序鏈表結(jié)構(gòu)使得可以按照鍵值排序的次序遍歷全部記錄。
B+Tree 在作為索引結(jié)構(gòu)時(shí)能夠帶來(lái)的好處有：
一，I/O 次數(shù)更少。這是因?yàn)樯衔囊舱f(shuō)過(guò)，BTree 的節(jié)點(diǎn)是存放在內(nèi)存頁(yè)中的。那么在相同的內(nèi)存頁(yè)大小（一般為4k）的情況下，B+Tree 能夠存儲(chǔ)更多的鍵值，那么整體樹(shù)結(jié)構(gòu)的高度就會(huì)更小，需要的 I/O 次數(shù)也就越小。
二，數(shù)據(jù)遍歷更為方便。這個(gè)優(yōu)勢(shì)很明顯是由有序鏈表帶來(lái)的。通過(guò)葉子節(jié)點(diǎn)的鏈接，使得對(duì)所有數(shù)據(jù)的遍歷只需要在線性的鏈表上完成，這就非常適合區(qū)間檢索和范圍查詢。
三，查詢性能更穩(wěn)定。這自然是由于只在葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，所以所有數(shù)據(jù)的查詢都會(huì)到達(dá)葉子節(jié)點(diǎn)，同時(shí)葉子節(jié)點(diǎn)的高度都相同，因此理論上來(lái)說(shuō)所有數(shù)據(jù)的查詢速度都是一致的。
正是由于 B+Tree 優(yōu)秀的結(jié)構(gòu)特性，使得常用作索引的實(shí)現(xiàn)結(jié)構(gòu)。在 MySQL 中，存儲(chǔ)引擎 MyISAM 和 InnoDB 都分別以 B+Tree 實(shí)現(xiàn)了響應(yīng)的索引設(shè)計(jì)。
物理存儲(chǔ)
雖說(shuō) B+Tree 結(jié)構(gòu)都可以用在 MyISAM 和 InnoDB，但是這二者對(duì)索引的在物理存儲(chǔ)層次的實(shí)現(xiàn)方式卻不相同。InnoDB 實(shí)現(xiàn)的是聚簇索引，而 MyISAM 實(shí)現(xiàn)的卻是非聚簇索引。在介紹聚簇索引之前，我們需要先了解以下啥是佩奇，不對(duì)，是啥是「主鍵索引」和「輔助索引」。
其實(shí)概念很簡(jiǎn)單。我們剛剛不是在講 B+Tree 的時(shí)候說(shuō)過(guò)，樹(shù)的非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值。沒(méi)錯(cuò)就是這個(gè)鍵值，當(dāng)這個(gè)鍵值是數(shù)據(jù)表的主鍵時(shí)，那么所建立的就是主鍵索引；當(dāng)這個(gè)鍵值是其它字段的時(shí)候，就是輔助索引。因而可以得出，主鍵索引只能有一個(gè)，而輔助索引卻可以有很多個(gè)。
聚簇索引和非聚簇索引的區(qū)別也就是根據(jù)其對(duì)應(yīng)的主鍵索引和輔助索引的不同特點(diǎn)而實(shí)現(xiàn)的。
說(shuō)回聚簇索引。先丟個(gè)定義。
聚簇索引的主鍵索引的葉子結(jié)點(diǎn)存儲(chǔ)的是鍵值對(duì)應(yīng)的數(shù)據(jù)本身；輔助索引的葉子結(jié)點(diǎn)存儲(chǔ)的是鍵值對(duì)應(yīng)的數(shù)據(jù)的主鍵鍵值。
這句話的信息量挺大的。首先，分析第一句話，主鍵索引的葉子節(jié)點(diǎn)存儲(chǔ)的是鍵值對(duì)應(yīng)的數(shù)據(jù)本身。
我們知道，主鍵索引存儲(chǔ)的鍵值就是主鍵。那么也就是說(shuō)，聚簇索引的主鍵索引，在葉子節(jié)點(diǎn)中存儲(chǔ)的是主鍵和主鍵對(duì)應(yīng)的數(shù)據(jù)。數(shù)據(jù)和主鍵索引是存儲(chǔ)在一起的，一起作為葉子節(jié)點(diǎn)的一部分。
然后，分析第二句話，輔助索引的葉子結(jié)點(diǎn)存儲(chǔ)的是鍵值對(duì)應(yīng)的數(shù)據(jù)的主鍵鍵值。
我們又知道，輔助索引存儲(chǔ)的鍵值是非主鍵的字段。那就也就是說(shuō)，通過(guò)輔助索引，可以找到非主鍵字段對(duì)應(yīng)的數(shù)據(jù)行中的主鍵。
重點(diǎn)來(lái)了。當(dāng)然主鍵索引和輔助索引一結(jié)合，能干啥呢。當(dāng)直接采用主鍵進(jìn)行檢索時(shí)，可通過(guò)主鍵索引直接獲得數(shù)據(jù)；而當(dāng)采用非主鍵進(jìn)行檢索時(shí)，先需要通過(guò)輔助索引來(lái)獲得主鍵，然后再通過(guò)這個(gè)主鍵在主鍵索引中找到對(duì)應(yīng)的數(shù)據(jù)行。
舉個(gè)例子吧。假設(shè)有這么一個(gè)數(shù)據(jù)表。
那么采用聚簇索引的存儲(chǔ)方式，對(duì)應(yīng)的主鍵索引為：（主鍵為ID）
對(duì)應(yīng)的輔助索引為：（鍵值為Name，大概的意思）：
所以當(dāng)使用where ID=7這樣的條件查找主鍵，則按照B+樹(shù)的檢索算法即可查找到對(duì)應(yīng)的葉節(jié)點(diǎn)，之后獲得行數(shù)據(jù)。對(duì)Name列進(jìn)行條件搜索，則需要兩個(gè)步驟：第一步在輔助索引B+樹(shù)中檢索Name，到達(dá)其葉子節(jié)點(diǎn)獲取對(duì)應(yīng)的主鍵。第二步使用主鍵在主鍵索引B+樹(shù)種再執(zhí)行一次B+樹(shù)檢索操作，最終到達(dá)葉子節(jié)點(diǎn)即可獲取整行數(shù)據(jù)。
最后把以上過(guò)程整理總結(jié)一下，聚簇索引實(shí)際上的過(guò)程就分為以下兩個(gè)過(guò)程。現(xiàn)在這個(gè)圖應(yīng)該能夠看懂了吧。
學(xué)完了聚簇索引，非聚簇索引就簡(jiǎn)單多啦。同樣，先上定義。
非聚簇索引的主鍵索引和輔助索引幾乎是一樣的，只是主索引不允許重復(fù)，不允許空值，他們的葉子結(jié)點(diǎn)都存儲(chǔ)指向鍵值對(duì)應(yīng)的數(shù)據(jù)的物理地址。
與聚簇索引來(lái)對(duì)比著看，上面的定義能夠說(shuō)明什么呢。首先，主鍵索引和輔助索引的葉子結(jié)點(diǎn)都存儲(chǔ)著鍵值對(duì)應(yīng)的數(shù)據(jù)的物理地址，這說(shuō)明無(wú)論是主鍵索引還是輔助索引都能夠通過(guò)直接獲得數(shù)據(jù)，而不需要像聚簇索引那樣在檢索輔助索引時(shí)還得多繞一圈。
同時(shí)還說(shuō)明一個(gè)點(diǎn)，葉子結(jié)點(diǎn)存儲(chǔ)的是物理地址，那么表示數(shù)據(jù)實(shí)際上是存在另一個(gè)地方的，并不是存儲(chǔ)在B+樹(shù)的結(jié)點(diǎn)中。這說(shuō)明非聚簇索引的數(shù)據(jù)表和索引表是分開(kāi)存儲(chǔ)的。
同樣，對(duì)非聚簇索引的檢索過(guò)程來(lái)個(gè)總結(jié)。
無(wú)論是主鍵索引還是輔助索引的檢索過(guò)程，都只需要通過(guò)相應(yīng)的 B+Tree 進(jìn)行搜索即可獲得數(shù)據(jù)對(duì)應(yīng)的物理地址，然后經(jīng)過(guò)依次磁盤(pán) I/O 就可訪問(wèn)數(shù)據(jù)。
對(duì)比聚簇索引和非聚簇索引，可以發(fā)現(xiàn)二者最主要的區(qū)別就是在于是否在 B+Tree 的節(jié)點(diǎn)中存儲(chǔ)數(shù)據(jù)，也就是數(shù)據(jù)和索引是否存儲(chǔ)在一起。這個(gè)區(qū)別導(dǎo)致最大的問(wèn)題就是聚簇索引的索引的順序和數(shù)據(jù)本身的順序是相同的，而非聚簇索引的順序跟數(shù)據(jù)的順序沒(méi)有啥關(guān)系。
介紹了這么多的索引，其實(shí)最終都是為了建立高性能的索引策略，對(duì)數(shù)據(jù)庫(kù)中的索引進(jìn)行優(yōu)化。索引的優(yōu)化有很多角度，針對(duì)特定的業(yè)務(wù)場(chǎng)景可采用不同的優(yōu)化策略。這里考慮到文章篇幅，就不具體介紹，下次再出一篇專門(mén)講索引優(yōu)化的文章。簡(jiǎn)單列舉一下在進(jìn)行優(yōu)化時(shí)可以考慮的幾個(gè)方向：
1 獨(dú)立的列。索引列不能是表達(dá)式的一部分，也不能是函數(shù)的參數(shù)。
2 前綴索引和索引選擇性。這二者實(shí)際上是相互制約的關(guān)系，制約條件在于前綴的長(zhǎng)度。一般應(yīng)選擇足夠長(zhǎng)的前綴以保證較高的選擇性（保證查詢效率），同時(shí)又不能太長(zhǎng)以便節(jié)省空間。
3 盡量使用覆蓋索引。覆蓋索引是指一個(gè)索引包含所有需要查詢的字段的值，這樣在查詢時(shí)只需要掃描索引而無(wú)須再去讀取數(shù)據(jù)行，從而極大的提高性能。
4 使用索引掃描來(lái)做排序。要知道，掃描索引本身是很快的，在設(shè)計(jì)索引時(shí)，可盡可能的使用同一個(gè)索引既滿足排序，又滿足查找行數(shù)據(jù)。
最后，在建立索引時(shí)給幾個(gè)小貼士：
1 優(yōu)先使用自增key作為主鍵
2 記住最左前綴匹配原則
3 索引列不能參與計(jì)算
4 選擇區(qū)分度高的列作索引
5 能擴(kuò)展就不要新建索引
索引的概念和原理是我們?cè)诹私夂途〝?shù)據(jù)庫(kù)過(guò)程中無(wú)法逃避的重點(diǎn)，而事實(shí)上建立高性能的索引對(duì)實(shí)際的應(yīng)用場(chǎng)景也具有重要意義。本文的目的依舊是由淺入深的介紹索引這么個(gè)東西，從概念到實(shí)現(xiàn)再到最終的優(yōu)化策略。
點(diǎn)到為止，學(xué)無(wú)止境。掌握了基本的理論和概念后，還需要在實(shí)際的服務(wù)器開(kāi)發(fā)場(chǎng)景中針對(duì)具體的問(wèn)題和服務(wù)進(jìn)行索引優(yōu)化方案的設(shè)計(jì)和使用。功力不夠，仍需努力。
高性能 MySQL，Baron Schwartz 等人著，電子工業(yè)出版社
公眾號(hào)碼海系列文章：
https://www.jianshu.com/p/9e9aca844c13
https://www.runoob.com/mysql/mysql-index.html
https://www.cnblogs.com/Aiapple/p/5693239.html
https://blog.csdn.net/tongdanping/article/details/79878302
https://www.cnblogs.com/igoodful/p/9361500.html
擊上方關(guān)注，All in AI中國(guó)
作者：Leonard Fink
在我們之前的博文中，我們討論了如何更新Dropbox搜索引擎，以將智能添加到用戶的工作流程中，以及我們?nèi)绾螛?gòu)建光學(xué)字符識(shí)別（OCR）管道。用戶將從這些變化中看到的最具影響力的好處之一是，Dropbox Professional和Dropbox Business Advanced 和企業(yè)計(jì)劃的用戶可以使用我們描述為自動(dòng)圖像文本識(shí)別的系統(tǒng)在圖像和PDF中搜索英文文本。
自動(dòng)識(shí)別圖像中的文本（包括包含圖像的PDF）的潛在好處是巨大的。人們?cè)贒ropbox中存儲(chǔ)了超過(guò)200億個(gè)圖像和PDF文件。在這些文件中，10%-20％是文檔類收據(jù)和白板圖像的照片，而不是文檔本身。這些現(xiàn)在是自動(dòng)圖像文本識(shí)別的候選者。同樣，這些PDF中有25％的文件是掃描文檔，這些文檔也是自動(dòng)文本識(shí)別的候選對(duì)象。
從計(jì)算機(jī)視覺(jué)的角度來(lái)看，雖然文檔和文檔圖像可能看起來(lái)與人類查看看非常相似，但計(jì)算機(jī)看到這些文件的方式有很大差異：文檔可以被編入索引以供搜索，允許用戶通過(guò)輸入找到它文件中的一些單詞。搜索索引系統(tǒng)的圖像是不透明的，因?yàn)樗伙@示為像素集合。圖像格式（如JPEG，PNG或GIF）通常不可索引，因?yàn)樗鼈儧](méi)有文本內(nèi)容，而基于文本的文檔格式（如TXT，DOCX或HTML）通常是可索引的。PDF文件介于這二者之間，因?yàn)樗鼈兛梢园谋竞蛨D像內(nèi)容的混合。自動(dòng)圖像文本識(shí)別能夠智能地區(qū)分所有這些文檔，以對(duì)包含在其中的數(shù)據(jù)進(jìn)行分類。
現(xiàn)在，當(dāng)用戶搜索出現(xiàn)在這些文件中的英文文本時(shí)，它會(huì)出現(xiàn)在搜索結(jié)果中。這篇文章描述了我們是如何構(gòu)建這個(gè)特性的。
評(píng)估挑戰(zhàn)
首先，我們著手衡量任務(wù)的規(guī)模，特別是試圖了解我們必須處理的數(shù)據(jù)量。這不僅可以告知成本估算，還可以確認(rèn)其有用性。更具體地說(shuō)，我們想回答以下問(wèn)題： ·我們應(yīng)該處理哪些類型的文件？ ·哪些文件可能具有"OCR-able"內(nèi)容？ ·對(duì)于像PDF這樣的多頁(yè)文檔類型，我們需要處理多少頁(yè)才能使其有用？
我們要處理的文件類型是那些當(dāng)前沒(méi)有可索引文本內(nèi)容的文件。這包括沒(méi)有文本數(shù)據(jù)的圖像格式和PDF文件。但是，并非所有圖像或PDF都包含文本。事實(shí)上，大多數(shù)只是沒(méi)有任何文字的照片或插圖。因此，一個(gè)關(guān)鍵的構(gòu)建模塊是一個(gè)機(jī)器學(xué)習(xí)模型，可以確定某個(gè)內(nèi)容是否具有OCR能力，換句話說(shuō)，它是否具有很有可能被我們的OCR系統(tǒng)識(shí)別的文本。這包括，例如，文檔的掃描或照片，但不包括具有隨機(jī)路牌的圖像之類的東西。我們訓(xùn)練的模型是一個(gè)卷積神經(jīng)網(wǎng)絡(luò)，它在將輸出轉(zhuǎn)換成關(guān)于它是否可能具有文本內(nèi)容的二元決策之前獲取輸入圖像。
對(duì)于圖像，最常見(jiàn)的圖像類型是JPEG，我們發(fā)現(xiàn)大約9％的JPEG可能包含文本。對(duì)于PDF文件，情況稍微復(fù)雜一些，因?yàn)镻DF文件可以包含多個(gè)頁(yè)面，并且每個(gè)頁(yè)面可以存在三個(gè)類別之一： ·頁(yè)面具有已嵌入和可索引的文本 ·頁(yè)面具有文本，但僅以圖像的形式，因此當(dāng)前不可索引 ·頁(yè)面沒(méi)有實(shí)質(zhì)性的文本內(nèi)容
我們希望略過(guò)第1類和第3類中的頁(yè)面，并只關(guān)注第2類，因?yàn)檫@是我們可以提供好處的地方。事實(shí)證明，3類中的每類分布分別為69％、28％和3％。總體而言，我們的目標(biāo)用戶的JPEG數(shù)量大約是PDF的兩倍，但每個(gè)PDF平均有8.8頁(yè)，而PDF包含文本圖像的可能性要高得多，所以就系統(tǒng)上的總體負(fù)載而言，PDF的貢獻(xiàn)將超過(guò)JPEG的10倍！然而，事實(shí)證明，通過(guò)下面描述的簡(jiǎn)單分析，我們可以顯著減少這個(gè)數(shù)字。
頁(yè)面總數(shù)
一旦我們決定了文件類型并開(kāi)發(fā)了每頁(yè)上可以使用OCR內(nèi)容的估計(jì)值，我們就希望對(duì)處理每個(gè)文件的方式保持戰(zhàn)略性。某些PDF文檔有很多頁(yè)面，因此處理這些文件的成本更高。幸運(yùn)的是，對(duì)于長(zhǎng)文檔，我們可以利用這樣一個(gè)事實(shí)，即使索引幾頁(yè)也可能使文檔更容易從搜索中訪問(wèn)。因此，我們查看了PDF樣本中頁(yè)面計(jì)數(shù)的分布情況，以確定每個(gè)文件最多可以索引多少頁(yè)面。事實(shí)證明，一半的PDF只有1頁(yè)，大約90％有10頁(yè)或更少。因此，我們采用了10頁(yè)的上限，也就是每個(gè)文檔中的前10頁(yè)。這意味著我們完全索引了近90％的文檔，并且索引剩余文檔的足夠頁(yè)面以使其可搜索。
自動(dòng)圖像文本識(shí)別系統(tǒng)組件
渲染
一旦我們開(kāi)始在所有OCR文件上使用OCR提取文本的過(guò)程，我們意識(shí)到我們有兩個(gè)選項(xiàng)來(lái)渲染嵌入在PDF文件中的圖像數(shù)據(jù)：我們可以提取嵌入在文件中的所有光柵（即像素）圖像對(duì)象單獨(dú)流，或者我們可以將PDF的整個(gè)頁(yè)面渲染為柵格圖像數(shù)據(jù)。在對(duì)兩者進(jìn)行實(shí)驗(yàn)之后，我們選擇了后者，因?yàn)槲覀円呀?jīng)為我們的文件預(yù)覽功能提供了強(qiáng)大的大規(guī)模PDF渲染基礎(chǔ)架構(gòu)。使用此系統(tǒng)的一些好處包括：
我們的預(yù)覽基礎(chǔ)架構(gòu)中使用的服務(wù)器端渲染基于PDF，這是Chromium項(xiàng)目中的PDF渲染器，這是一個(gè)由Google啟動(dòng)的開(kāi)源項(xiàng)目，是Chrome瀏覽器的基礎(chǔ)。相同的軟件也用于正文檢測(cè)并確定文檔是否是"僅限于圖像"，這有助于決定我們是否要應(yīng)用OCR處理。
一旦開(kāi)始渲染，每個(gè)文檔的頁(yè)面將被并行處理以降低延遲，根據(jù)我們上面的分析，以前10頁(yè)為上限。我們渲染每個(gè)頁(yè)面的分辨率填充2048×2048像素的矩形，保留縱橫比。
文檔圖像分類
我們的OCR機(jī)器學(xué)習(xí)模型最初是為Dropbox文檔掃描儀功能而構(gòu)建的，目的是為了確定用戶最近拍攝的（正常）照片是否可以建議他們"變成掃描"。這個(gè)分類器是使用線性分類器構(gòu)建的在預(yù)先訓(xùn)練的ImageNet模型（GoogLeNet / Inception）的圖像特征之上。它接受了從幾個(gè)不同來(lái)源收集的數(shù)千張圖像的訓(xùn)練，包括公共圖像、用戶捐贈(zèng)的圖像和一些Dropbox員工捐贈(zèng)的圖像。原始開(kāi)發(fā)版本是使用Caffe構(gòu)建的，之后該模型轉(zhuǎn)換為T(mén)ensorFlow，以與我們的其他部署保持一致。 在微調(diào)這個(gè)組件的性能時(shí)，我們學(xué)到了一個(gè)重要的教訓(xùn)：在開(kāi)始時(shí)，分類器偶爾會(huì)產(chǎn)生誤報(bào)（它認(rèn)為包含文本的圖像，但實(shí)際上沒(méi)有），例如空白墻壁、天際線或開(kāi)闊水域的圖片。盡管它們看起來(lái)與人眼完全不同，但是分類器在所有這些圖像中都看到了相似的東西：它們都具有平滑的背景和水平線條。通過(guò)迭代標(biāo)記并將這種所謂的"難分樣本(hard negatives)"添加到訓(xùn)練集中，我們顯著提高了分類的精確度，有效地教授了分類器，即使這些圖像具有文本文檔的許多特征，它們也不包含實(shí)際文本。
角點(diǎn)檢測(cè)
在圖像中定位文檔的角并定義其（大致）四邊形是字符識(shí)別之前的另一個(gè)關(guān)鍵步驟。給定角的坐標(biāo)，可以通過(guò)簡(jiǎn)單的幾何變換來(lái)校正圖像中的文檔（制成直角矩形）。文檔角點(diǎn)檢測(cè)器組件使用另一個(gè)ImageNet深度卷積網(wǎng)絡(luò)（Densenet-121）構(gòu)建，其頂層由產(chǎn)生四角坐標(biāo)的回歸器替代。
用于訓(xùn)練該模型的測(cè)試數(shù)據(jù)僅使用數(shù)百個(gè)圖像。四個(gè)或更多定義封閉文檔邊界多邊形的2-D點(diǎn)形式的標(biāo)簽也由Mechanical Turk工作人員使用定制的用戶界面（UI）繪制，并通過(guò)機(jī)器學(xué)習(xí)團(tuán)隊(duì)成員的注釋進(jìn)行擴(kuò)充。通常，包含在訓(xùn)練圖像中的文檔的一個(gè)或多個(gè)角落位于圖像邊界之外，需要人類直覺(jué)來(lái)填充缺失的數(shù)據(jù)。
由于深度卷積網(wǎng)絡(luò)被饋送按比例縮小的圖像，因此四邊形的原始預(yù)測(cè)位置的分辨率低于原始圖像。為了提高精度，我們采用兩步流程：
（1）獲得初始的四邊形
（2）在每個(gè)角落的較高分辨率補(bǔ)丁上運(yùn)行另一個(gè)回歸
從四邊形的坐標(biāo)，可以很容易地將圖像校正為對(duì)齊的版本。
令牌提取
在我們之前的博客文章中描述了實(shí)際的光學(xué)字符識(shí)別系統(tǒng)，它提取文本標(biāo)記（大致對(duì)應(yīng)于單詞）。它將來(lái)自角點(diǎn)檢測(cè)步驟的校正后的圖像作為輸入，并生成令牌檢測(cè)，其中包括令牌的邊界框和每個(gè)令牌的文本。這些被排列成大致順序的令牌列表并添加到搜索索引中。如果有多個(gè)頁(yè)面，則每個(gè)頁(yè)面上的標(biāo)記列表將串聯(lián)在一起以生成一個(gè)大列表。
把碎片拼在一起
要為所有符合條件的用戶在所有可能可索引的文件上運(yùn)行自動(dòng)圖像文本識(shí)別，我們需要一個(gè)可以攝取傳入文件事件（例如，添加或編輯）并啟動(dòng)相關(guān)處理的系統(tǒng)。事實(shí)證明，這是Cape的一個(gè)自然用例，這是一種靈活的、大規(guī)模、低延遲的異步事件流處理框架，支持許多Dropbox功能。作為一般搜索索引框架的一部分，我們?yōu)镺CR處理添加了一個(gè)新的Cape微服務(wù)工作者（稱為"lambda"）。
處理的前幾個(gè)步驟利用了Dropbox的一般預(yù)覽基礎(chǔ)設(shè)施。這是一個(gè)可以有效地將二進(jìn)制文件作為輸入并返回此文件的轉(zhuǎn)換的系統(tǒng)。例如，它可能需要一個(gè)PowerPoint文件并生成該P(yáng)owerPoint文件的縮略圖。該系統(tǒng)可通過(guò)插件進(jìn)行擴(kuò)展，這些插件對(duì)特定類型的文件進(jìn)行操作并返回特定的轉(zhuǎn)換。因此，添加新文件類型或轉(zhuǎn)換很容易。最后，系統(tǒng)還有效地緩存轉(zhuǎn)換，因此如果我們嘗試兩次生成相同PowerPoint文件的縮略圖圖像，那么昂貴的縮略圖操作只會(huì)運(yùn)行一次。
我們?yōu)榇斯δ芫帉?xiě)了幾個(gè)預(yù)覽插件，包括（數(shù)字對(duì)應(yīng)于上面的系統(tǒng)圖）：
穩(wěn)健性
為了在遠(yuǎn)程調(diào)用期間出現(xiàn)瞬態(tài)/臨時(shí)錯(cuò)誤的情況下提高系統(tǒng)的穩(wěn)健性，我們使用抖動(dòng)指數(shù)退避重試遠(yuǎn)程調(diào)用，這是分布式系統(tǒng)中的最佳實(shí)踐技術(shù)。例如，通過(guò)第二次和第三次重試，我們將PDF元數(shù)據(jù)提取的失敗率降低了88％。
性能優(yōu)化
當(dāng)我們將管道的初始版本部署到一小部分流量進(jìn)行測(cè)試時(shí)，我們發(fā)現(xiàn)機(jī)器學(xué)習(xí)模型（角點(diǎn)檢測(cè)、方向檢測(cè)、OCR等）的計(jì)算開(kāi)銷將需要一個(gè)龐大的集群，這會(huì)使該特性過(guò)于昂貴部署。此外，我們發(fā)現(xiàn)看到的流量大約是我們根據(jù)歷史增長(zhǎng)率估算的流量的2倍。
為了解決這個(gè)問(wèn)題，我們首先提高了OCR機(jī)器學(xué)習(xí)模型的吞吐量，并假設(shè)增加吞吐量可以最大限度地減少我們需要的OCR集群的大小。
為了實(shí)現(xiàn)準(zhǔn)確可控的基準(zhǔn)測(cè)試，我們構(gòu)建了專用的沙箱環(huán)境和命令行工具，使我們能夠?qū)⑤斎霐?shù)據(jù)發(fā)送到多個(gè)子服務(wù)，以分別測(cè)量每個(gè)子服務(wù)的吞吐量和延遲。我們用于基準(zhǔn)測(cè)試的秒表日志是從實(shí)際實(shí)時(shí)流量中采樣的，沒(méi)有殘留數(shù)據(jù)收集。
從配置參數(shù)開(kāi)始，我們選擇從外部進(jìn)入性能優(yōu)化。在處理受CPU限制的機(jī)器學(xué)習(xí)瓶頸時(shí)，有時(shí)可以通過(guò)簡(jiǎn)單的配置和庫(kù)更改來(lái)實(shí)現(xiàn)大的性能提升;我們將在下面討論幾個(gè)例子。
第一個(gè)提升來(lái)自為jails中運(yùn)行的代碼選擇正確的并發(fā)度：為了安全起見(jiàn)，我們運(yùn)行大多數(shù)直接觸及軟件監(jiān)獄中用戶內(nèi)容的代碼，這些代碼限制了可以運(yùn)行的操作，隔離來(lái)自不同用戶的內(nèi)容以防止軟件錯(cuò)誤從破壞數(shù)據(jù)，并保護(hù)我們的基礎(chǔ)設(shè)施免受惡意威脅向量。我們通常在一臺(tái)機(jī)器上為每個(gè)核心部署一個(gè)jail，以實(shí)現(xiàn)最大的并發(fā)性，同時(shí)允許每個(gè)jail只運(yùn)行單線程代碼（即數(shù)據(jù)并行）。
然而，事實(shí)證明，我們用于預(yù)測(cè)像素中的字符的TensorFlow深度學(xué)習(xí)框架默認(rèn)配置了多核支持。這意味著每個(gè)jail現(xiàn)在都運(yùn)行多線程代碼，這導(dǎo)致了大量的場(chǎng)景切換開(kāi)銷。因此，通過(guò)關(guān)閉TensorFlow中的多核支持，我們能夠?qū)⑼掏铝刻岣呒s3倍。
在這個(gè)修復(fù)之后，我們發(fā)現(xiàn)性能仍然太慢 - 甚至在我們的機(jī)器學(xué)習(xí)模型之前，請(qǐng)求就會(huì)出現(xiàn)瓶頸！一旦我們針對(duì)使用的CPU核心數(shù)量調(diào)整了預(yù)分配的jail和RPC服務(wù)器實(shí)例的數(shù)量，我們終于開(kāi)始獲得預(yù)期的吞吐量。通過(guò)在TensorFlow中啟用矢量化AVX2指令，并通過(guò)TensorFlow XLA將模型和運(yùn)行時(shí)預(yù)編譯到C ++庫(kù)中，我們得到了額外的顯著提升。最后，我們對(duì)模型進(jìn)行了基準(zhǔn)測(cè)試，發(fā)現(xiàn)狹窄中間層上的2D卷積是熱點(diǎn)，并通過(guò)在圖表中手動(dòng)展開(kāi)它們來(lái)加速它們。
文檔圖像流水線的兩個(gè)重要組成部分是角點(diǎn)檢測(cè)和方向預(yù)測(cè)，兩者都使用深度卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)。與我們之前使用過(guò)的Inception-Resnet-v2模型相比，我們發(fā)現(xiàn)Densenet-121的速度幾乎快兩倍，而且在預(yù)測(cè)文檔角落位置方面的準(zhǔn)確性稍差。為了確保我們沒(méi)有在準(zhǔn)確性上回歸太多，我們進(jìn)行了A/B測(cè)試以評(píng)估對(duì)可用性的實(shí)際影響，比較用戶手動(dòng)校正自動(dòng)預(yù)測(cè)文檔角落的頻率。我們得出結(jié)論，差異可以忽略不計(jì)，并且性能的提升是值得的。
為未來(lái)的智能功能鋪平道路
使文檔圖像可搜索是向更加深入理解文檔結(jié)構(gòu)和內(nèi)容的第一步。有了這些信息，Dropbox可以幫助用戶更好地整理文件，這是邁向更開(kāi)明的工作方式的一步。
自動(dòng)圖像文本識(shí)別是Dropbox工程師處理的涉及計(jì)算機(jī)視覺(jué)和機(jī)器學(xué)習(xí)的大型項(xiàng)目類型的主要示例。
者：Jia-Xin
cnblogs.com/YangJiaXin/p/11153579.html
用MATCH() … AGAINST 方式來(lái)進(jìn)行搜索
match()表示搜索的是那個(gè)列，against表示要搜索的是那個(gè)字符串
查看默認(rèn)的分詞（以這些詞來(lái)區(qū)分不同的關(guān)鍵詞）；也可以自定義分詞，以這些詞來(lái)區(qū)分不同的關(guān)鍵詞SELECT * FROM information_schema.INNODB_FT_DEFAULT_STOPWORD;
如
natural language search（自然語(yǔ)言搜索）
通過(guò)MATCH AGAINST 傳遞某個(gè)特定的字符串來(lái)進(jìn)行檢，默認(rèn)方式
boolean search（布爾搜索）
為檢索的字符串增加操作符，如“+”表示必須包含，"-"不包含，"*" 表示通配符，即使傳遞的字符串較小或出現(xiàn)在停詞中，也不會(huì)被過(guò)濾掉
query expansion search（查詢擴(kuò)展搜索）
搜索字符串用于執(zhí)行自然語(yǔ)言搜索，然后，搜索返回的最相關(guān)行的單詞被添加到搜索字符串，并且再次進(jìn)行搜索，查詢將返回來(lái)自第二個(gè)搜索的行
配置相關(guān)參數(shù)
innodb_ft_min_token_size默認(rèn)3，表示最小3個(gè)字符作為一個(gè)關(guān)鍵詞，增大該值可減少全文索引的大小
innodb_ft_max_token_size默認(rèn)84，表示最大84個(gè)字符作為一個(gè)關(guān)鍵詞，限制該值可減少全文索引的大小
ngram_token_size默認(rèn)2，表示2個(gè)字符作為內(nèi)置分詞解析器的一個(gè)關(guān)鍵詞，如對(duì)“abcd”建立全文索引，關(guān)鍵詞為'ab'，'bc'，'cd'
當(dāng)使用ngram分詞解析器時(shí)，innodb_ft_min_token_size和innodb_ft_max_token_size 無(wú)效
注意 這三個(gè)參數(shù)均不可動(dòng)態(tài)修改，修改了這些參數(shù)，需重啟MySQL服務(wù)，并重新建立全文索引
1、目標(biāo)
2、設(shè)置以下參數(shù)減少磁盤(pán)IO壓力
SET GLOBAL sync_binlog=100;
SET GLOBAL innodb_flush_log_at_trx_commit=2;3、導(dǎo)入1kw 數(shù)據(jù)進(jìn)行測(cè)試全文索引
該數(shù)據(jù)來(lái)源網(wǎng)上搜索
https://pan.baidu.com/s/1aaB1R3bkBGZRMEx0o6T61w 提取碼：60l7
4、某個(gè)文章表 的結(jié)構(gòu)
使用myloader 多線程導(dǎo)入測(cè)試數(shù)據(jù)
-- 先把測(cè)試數(shù)據(jù)進(jìn)行解壓
tar -zxf mydumper_dump_article.tar.gz
time myloader -u $user -p $passwd -S $socket -t 32 -d /datas/dump_article -v 35、導(dǎo)入數(shù)據(jù)后總數(shù)據(jù)量和數(shù)據(jù)文件、索引文件大小
SELECT COUNT(*) FROM `article`;
+----------+
| COUNT(*) |
+----------+
| 10000000 |
+----------+
1 row in set (7.85 sec)
SELECT table_name, CONCAT(FORMAT(SUM(data_length) / 1024 / 1024,2),'M') AS dbdata_size, CONCAT(FORMAT(SUM(index_length) / 1024 / 1024,2),'M') AS dbindex_size, CONCAT(FORMAT(SUM(data_length + index_length) / 1024 / 1024 / 1024,2),'G') AS `db_size(G)`, AVG_ROW_LENGTH,table_rows,update_time FROM information_schema.tables WHERE table_schema = DATABASE() and table_name='article';
+------------+-------------+--------------+------------+----------------+------------+---------------------+
| table_name | dbdata_size | dbindex_size | db_size(G) | AVG_ROW_LENGTH | table_rows | update_time |
+------------+-------------+--------------+------------+----------------+------------+---------------------+
| article | 3,710.00M | 1,003.00M | 4.60G | 414 | 9388739 | 2019-07-05 15:31:37 |
+------------+-------------+--------------+------------+----------------+------------+---------------------+1、該表已有關(guān)鍵詞字段（對(duì)文章內(nèi)容的簡(jiǎn)述），并以“,”作為分詞符
2、不建全文索引時(shí)搜索某個(gè)關(guān)鍵詞
需要進(jìn)行全表掃描
my.cnf配置文件中設(shè)置innodb_ft_min_token_size，并重啟MySQL服務(wù)（最小兩個(gè)字符作為一個(gè)關(guān)鍵詞，默認(rèn)三個(gè)字符作為一個(gè)關(guān)鍵詞）
[mysqld]
innodb_ft_min_token_size=23.1 設(shè)置自定義stopwords（即分詞）
USE mysql;
CREATE TABLE my_stopwords(VALUE VARCHAR(30)) ENGINE = INNODB;
INSERT INTO my_stopwords(VALUE) VALUE (',');
SET GLOBAL innodb_ft_server_stopword_table = 'mysql/my_stopwords';~
SHOW GLOBAL VARIABLES WHERE Variable_name IN('innodb_ft_min_token_size','innodb_ft_server_stopword_table');
+---------------------------------+--------------------+
| Variable_name | Value |
+---------------------------------+--------------------+
| innodb_ft_min_token_size | 2 |
| innodb_ft_server_stopword_table | mysql/my_stopwords |
+---------------------------------+--------------------+3.2 創(chuàng)建全文索引
alter table article add fulltext index idx_full_keyword(keywords);
* [ ] Query OK, 0 rows affected, 1 warning (1 min 27.92 sec)
* [ ] Records: 0 Duplicates: 0 Warnings: 13.3 剩余磁盤(pán)空間需足夠，原表4.6G，剩余5.7G磁盤(pán)，添加全文索引也會(huì)失敗
3.4 利用創(chuàng)建的全文索引進(jìn)行查詢某個(gè)關(guān)鍵詞出現(xiàn)的次數(shù)
查詢響應(yīng)時(shí)間有了很大的提升，只需0.05s；使用where keywords like '%時(shí)尚%' 需要7.56s。推薦閱讀：MySQL性能優(yōu)化實(shí)踐（很全面，值得收藏）
3.5 如需同時(shí)完全匹配多個(gè)關(guān)鍵詞，用布爾全文搜索
表示完全匹配 "三里屯,北京" 的記錄數(shù)
select count(*) from article where match(keywords) against('+三里屯,北京' in boolean mode);
+----------+
| count(*) |
+----------+
| 1 |
+----------+
1 row in set (0.06 sec)表示匹配“三里屯” 或者 “北京”的記錄數(shù)
select count(*) from article where match(keywords) against('三里屯,北京');
+----------+
| count(*) |
+----------+
| 8 |
+----------+
1 row in set (0.06 sec)3.6 創(chuàng)建全文索引后，會(huì)創(chuàng)建一些其它文件
96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_1.ibd96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_2.ibd96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_3.ibd96K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_4.ibd128K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_5.ibd256K Jul 5 16:30 FTS_00000000000000a7_00000000000000c0_INDEX_6.ibd96K Jul 5 16:29 FTS_00000000000000a7_BEING_DELETED_CACHE.ibd96K Jul 5 16:29 FTS_00000000000000a7_BEING_DELETED.ibd96K Jul 5 16:30 FTS_00000000000000a7_CONFIG.ibd96K Jul 5 16:29 FTS_00000000000000a7_DELETED_CACHE.ibd96K Jul 5 16:29 FTS_00000000000000a7_DELETED.ibd
1、對(duì)title字段建立全文索引（該字段沒(méi)有固定的stopwords 分詞，使用ngram分詞解析器）
需先在my.cnf 配置文件中設(shè)置ngram_token_size（默認(rèn)為2，2個(gè)字符作為ngram 的關(guān)鍵詞），并重啟mysql服務(wù)
這里使用默認(rèn)的 2
select title from article limit 10;
+------------------------------------------------------------------------------+
| title |
+------------------------------------------------------------------------------+
| worth IT |
|Launchpad 江南皮革廠小show |
|Raw 幕后罕見(jiàn)一刻 “瘋子”被抬回后臺(tái) |
|Raw:公子大罵老爸你就是個(gè)綠茶 公子以一打四 |
|四組30平米精裝小戶型，海量圖片，附戶型圖 |
|夜店女王性感煙熏貓眼妝 |
|大秀哥重摔“巨石”強(qiáng)森 |
|少女時(shí)代 崔秀英 服飾科普 林允兒 黃美英 金泰妍 鄭秀晶 |
|德陽(yáng)戶外踏青，花田自助燒烤 |
+------------------------------------------------------------------------------+2、對(duì)title字段創(chuàng)建全文索引
alter table article add fulltext index ft_index_title(title) with parser ngram;
Query OK, 0 rows affected (3 min 29.22 sec)
Records: 0 Duplicates: 0 Warnings: 03、會(huì)創(chuàng)建倒排索引（title字段越長(zhǎng)長(zhǎng)，創(chuàng)建的倒排索引越大）
112M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_1.ibd28M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_2.ibd20M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_3.ibd140M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_4.ibd128M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_5.ibd668M Jul 5 21:46 FTS_00000000000000a7_00000000000000cd_INDEX_6.ibd
4、不建立全文索引搜索title的某個(gè)關(guān)鍵詞
5、使用全文索引搜索某個(gè)關(guān)鍵詞
響應(yīng)時(shí)間有很大的提升
6、注意當(dāng)搜索的關(guān)鍵詞字符數(shù)大于2 （ngram_token_size定義大小）會(huì)出現(xiàn)不一致問(wèn)題
普通搜索，實(shí)際中出現(xiàn)該關(guān)鍵詞的記錄數(shù)為6
全文搜索，出現(xiàn)關(guān)鍵字的記錄數(shù)為9443
實(shí)際出現(xiàn)該關(guān)鍵字的記錄數(shù)為1
全文搜索出現(xiàn)該關(guān)鍵詞的記錄數(shù)為3202
當(dāng)mysql 某字段中有固定的stopword 分詞（英文的空格符，中文的“,”"-"等），對(duì)該字段建立全文索引，能快速搜索出現(xiàn)某個(gè)關(guān)鍵詞的相關(guān)記錄信息，實(shí)現(xiàn)簡(jiǎn)單搜索引擎的效果
當(dāng)mysql 某字段沒(méi)有固定的stopword 分詞，使用內(nèi)置解析器ngram 可將字段值分成固定數(shù)量（ngram_token_size定義大小）的關(guān)鍵詞快速進(jìn)行搜索；當(dāng)搜索的關(guān)鍵詞的字符數(shù)量不等于ngram_token_size定義大小時(shí)，會(huì)出現(xiàn)與實(shí)際情況不一致的問(wèn)題
全文索引能快速搜索，也存在維護(hù)索引的開(kāi)銷；字段長(zhǎng)度越大，創(chuàng)建的全文索引也越大，會(huì)影響DML語(yǔ)句的吞吐量，可用專門(mén)的全文搜索引擎ES來(lái)做這件事
*請(qǐng)認(rèn)真填寫(xiě)需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。
