萬字長文帶你詳解九大數據存儲引擎結構（下）

五．倒排索引存儲

對Mysql來說，采用B+樹索引，對Elasticsearch/Lucene來說，是倒排索引。倒排索引(Inverted Index)也叫反向索引，有反向索引必有正向索引。通俗地講，正向索引是通過key找value，反向索引則是通過value找key。

Elasticsearch是建立在全文搜索引擎庫Lucene基礎上的搜索引擎，它隱藏了Lucene的復雜性，提供一套簡單一致的RESTful API。Elasticsearch的倒排索引其實就是Lucene的倒排索引。

1.? Lucene 的倒排索引

倒排索引，通過Term搜索到文檔ID。首先想想看，世界上那么多單詞，中文、英文、日文、韓文 … 如每次搜索一個單詞都要全局遍歷一遍，明顯不行。于是有了對單詞進行排序，像B+樹一樣可在頁里實現二分查找。光排序還不行，單詞都放在磁盤，磁盤IO慢的不得了，大量存放內存會導致內存爆了。

下圖：通過字典把所有單詞都貼在目錄里。

Lucene的倒排索引，增加了最左邊的一層「字典樹」term index，它不存儲所有的單詞，只存儲單詞前綴，通過字典樹找到單詞所在的塊，也就是單詞的大概位置，再在塊里二分查找，找到對應的單詞，再找到單詞對應的文檔列表。

假設有多個term，如：Carla,Sara,Elin,Ada,Patty,Kate,Selena。找出某個特定term,可通過排序后以二分查找方式，logN次磁盤查找得到目標，但磁盤隨機讀操作較昂貴(單次Random access約10ms)。所以盡量少的讀磁盤，可把一些數據緩存到內存。但term dictionary太大，于是就有了term index.通過trie樹來構建index;

通過term index可快速定位term dictionary的某個offset，從這個位置再往后順序查找。再加上一些壓縮技術(FST)，term index 的尺寸可以只有所有term尺寸的幾十分之一，使得用內存緩存整個term index變成可能。

FST Tree

一種有限狀態轉移機，優點：1）空間占用小。通過對詞典中單詞前綴和后綴的重復利用，壓縮了存儲空間；2）查詢速度快。O(len(str))的查詢時間復雜度。

示例：對“cat”、 “deep”、 “do”、 “dog” 、“dogs”這5個單詞進行插入構建FST（必須已排序），得到如下一個有向無環圖。

FST壓縮率一般在3倍~20倍之間，相對于TreeMap/HashMap的膨脹3倍，內存節省就有9倍到60倍！

2.? 與MySQL檢索對比

MySQL只有term dictionary，以B-樹排序的方式存儲在磁盤上。檢索一個term需若干次random access磁盤操作。而Lucene在term dictionary的基礎上添加了term index來加速檢索，以樹的形式緩存在內存中。從term index查到對應term dictionary的block位置后，再去磁盤上找term，大大減少磁盤的random access次數。

Term index在內存中是以FST(finite state transducers)的壓縮形式保存，其特點是非常節省內存。Term dictionary在磁盤上是以分block的方式保存的，一個block內部利用公共前綴壓縮，比如都是Ab開頭的單詞就可以把Ab省去。這樣term dictionary可比B-樹更節約空間。

3.? 聯合索引結構及檢索

給定多個查詢過濾條件，如”age=18 AND gender=女”就是把兩個posting list做一個“與”的合并。對于MySql來說，如果給age和gender兩個字段都建立了索引，查詢時只會選擇其中最selective的來用，然后另一個條件是在遍歷行的過程中在內存中計算之后過濾掉。那如何聯合使用兩個索引呢？兩種辦法：

l? 使用skip list數據結構，同時遍歷gender和age的posting list，互相skip；

l? 使用bitset數據結構，對gender和age兩個filter分別求出 bitset，對兩個bitset做AND操作。

PostgreSQL從8.4版本開始支持通過bitmap聯合使用兩個索引，就是利用bitset數據結構來做的。一些商業的關系型數據庫也支持類似聯合索引的功能。

ES支持以上兩種的聯合索引方式，如果查詢的filter緩存到了內存中(以bitset形式），那么合并就是兩個bitset的AND。如果查詢的filter沒有緩存，那么就用skip list的方式去遍歷兩個on disk的posting list。

1)? 利用Skip List合并

即使對于排過序的鏈表，查找還是需要進行通過鏈表的指針進行遍歷，時間復雜度很高依然是O(n)，這個顯然不能接受。是否可以像數組那樣，通過二分法查找，但由于在內存中的存儲的不確定性，不能這么做。但可結合二分法思想，跳表就是鏈表與二分法的結合。跳表是有序鏈表。

l? 鏈表從頭節點到尾節點都是有序的

l? 可以進行跳躍查找(形如二分法），降低時間復雜度

說明：在上圖中如要找node6節點

1)? ?第一次比較headerNode->next[2]的值，即node5的值。顯然node5小于node6，所以，下一次應從第2級的node5開始查詢，令targetNode=targetNode->next[2];

2)? ?第二次應該比較node5->next[2]的值，即tailNode的值。tailNode的值是最大的，所以結果是大于，下一次應從第1級的node5開始查詢。這里從第2級跳到第1級。但沒有改變targetNode。

3)? ?第三次應該比較node5->next[1]的值，即node7的值。因node7大于node6，所以，下一次應該從第0級的node5開始查詢。這里從第1級跳到第0級。也沒有改變targetNode。

4)? ?第四次應該比較node5->next[0]的值，即node6的值。這時相等，結束。如果小于，targetNode往后移，改變targetNode=targetNode->next[0]，如果大于，則沒找到，結束。因為這已經是第0級，沒法再降了。

考慮到頻繁出現的term，如gender里的男或女。如有1百萬個文檔，那性別為男的posting list里就會有50萬個int值。用FOR編碼進行壓縮可極大減少磁盤占用,對于減少索引尺寸有非常重要的意義。當然MySql B-樹里也有類似的posting list，是未經這樣壓縮的。因為FOR的編碼有解壓縮成本,利用skip list，除了跳過了遍歷的成本，也跳過了解壓縮這些壓縮過的block的過程，從而節省了CPU。

Frame Of Reference

以下三個步驟組成了Frame Of Reference(FOR)壓縮編碼技術

Step 1：增量編碼

Step 2：分割成塊

Lucene每個塊是256個文檔ID，每個塊增量編碼后每個元素都不會超過256(1 byte).為方便演示，圖中假設每個塊是3個文檔ID。

Step 3：按需分配空間

對于第一個塊 [73, 227, 2]，最大元素是227，需要 8 bits，那給這個塊的每個元素，都分配8 bits的空間。但對于第二個塊[30,11,29]，最大才30，只需5bits，那給每個元素只分配5bits空間。這一步可說是精打細算，按需分配。

2)? 利用bitset合并

Bitset是一種很直觀的數據結構，posting list如:[1,3,4,7,10]對應的bitset就是:[1,0,1,1,0,0,1,0,0,1], 每個文檔按照文檔id排序對應其中的一個bit。Bitset自身就有壓縮的特點，其用一個byte就可以代表8個文檔。所以100萬個文檔只需要12.5萬個byte。但考慮到文檔可能有數十億之多，在內存里保存bitset仍然是很奢侈的事情。且對于每一個filter都要消耗一個bitset，比如age=18緩存起來的話是一個bitset，18<=age<25是另外一個filter,緩存起來也要一個bitset。所以需要一個數據結構：

l? 可以壓縮地保存上億個bit代表對應的文檔是否匹配filter；

l? 壓縮的bitset仍然可以很快地進行AND和OR的邏輯操作。

Roaring Bitmap

Lucene使用這個數據結構，其壓縮思路其實很簡單,與其保存100個0，占用100個bit，還不如保存0一次，然后聲明這個0重復了100遍。

bitmap不管有多少文檔，占用的空間都一樣。譬如一個數組里面只有兩個文檔ID：[0, 65535]，表示[1,0,0,0,….(很多個0),…,0,0,1]，需要65536個bit，也就是65536/8=8192 bytes。而用Integer數組只需2*2bytes=4 bytes。可見在文檔數量不多時使用Integer數組更節省內存。算一下臨界值，無論文檔數量多少，bitmap都需要8192bytes，而Integer數組則和文檔數量成線性相關，每個文檔ID占2bytes，所以8192/2=4096，當文檔數量少于4096時用Integer數組，否則用bitmap.

4.? 存儲文檔的減少方式

一種常見的壓縮存儲時間序列的方式是把多個數據點合并成一行。Opentsdb支持海量數據的一個絕招就是定期把很多行數據合并成一行，這個過程叫compaction。類似的vivdcortext使用MySql存儲的時候，也把一分鐘的很多數據點合并存儲到MySql的一行以減少行數。

ES可實現類似優化，那就是Nested Document。可把一段時間的很多個數據點打包存儲到一個父文檔里，變成其嵌套的子文檔。這樣可把數據點公共的維度字段上移到父文檔里，而不用在每個子文檔里重復存儲，從而減少索引的尺寸。

存儲時，無論父文檔還是子文檔，對于Lucene來說都是文檔，都會有文檔Id。但對于嵌套文檔來說，可以保存起子文檔和父文檔的文檔id是連續的，且父文檔總是最后一個。有這樣一個排序性作為保障，那么有一個所有父文檔的posting list就可跟蹤所有的父子關系。也可以很容易地在父子文檔id之間做轉換。把父子關系也理解為一個filter，那么查詢檢索的時候不過是又AND了另外一個filter而已。

使用了嵌套文檔之后，對于term的posting list只需要保存父文檔的docid就可，可以比保存所有的數據點的doc id要少很多。如可在一個父文檔里塞入50個嵌套文檔，那posting list可變成之前的1/50。

… … …

六．對象與塊存儲

本章節描述，以Ceph 分布式存儲系統為參考。

1.? 對象存儲結構

在文件系統一級提供服務，只是優化了目前的文件系統，采用扁平化方式，棄用了目錄樹結構，便于共享，高速訪問。

對象存儲體系結構定義了一個新的、更加智能化的磁盤接口OSD。OSD是與網絡連接的設備，包含存儲介質，如磁盤或磁帶，并具有足夠智能可管理本地存儲的數據。計算結點直接與OSD通信，訪問它存儲的數據，不需要文件服務器的介入。對象存儲結構提供的性能是目前其它存儲結構難以達到的，如ActiveScale對象存儲文件系統的帶寬可以達到10GB/s。

對象存儲的結構包括元數據服務器（控制節點MDS）和數據存儲服務器（OSD），兩者進行數據的存儲，還需客服端進行存儲的服務訪問和使用。

2.? 塊設備存儲

塊存儲技術的構成基礎是最下層的硬件存儲設備，可能是機械硬盤也可能是固態硬盤。一個操作系統下可以獨立控制多個硬件存儲設備，但這些硬件存儲設備的工作相對獨立，通過操作系統命令看到的也是幾個獨立的設備文件。通過陣列控制層的設備可以在同一個操作系統下協同控制多個存儲設備，讓后者在操作系統層被視為同一個存儲設備。

典型設備：磁盤陣列，硬盤，虛擬硬盤，這種接口通常以QEMU Driver或者Kernel Module的方式存在，接口需要實現Linux的Block Device的接口或者QEMU提供的Block Driver接口，如Sheepdog，AWS的EBS，阿里云的盤古系統，還有Ceph的RBD（RBD是Ceph面向塊存儲的接口）。

·? ? ? ?可通過Raid與LVM等手段對數據提供了保護;

·? ? ? ?多塊廉價的硬盤組合起來，提高容量;

·? ? ? ?多塊磁盤組合出來的邏輯盤，提升讀寫效率。

Ceph的RBD(RADOS Block Device)使用方式：先創建一個塊設備，然后映射塊設備到服務器，掛載后即可使用。

七．矩陣的存儲結構

說明：本章節以矩陣存儲為重心，而非矩陣的運算。

矩陣具有元素數目固定以及元素按下標關系有序排列等特點，所以在使用高級語言編程時，一般是用二維數組來存儲矩陣。數據庫表數據是行列存儲，可視為矩陣的應用形式。矩陣的存儲包括完全存儲和稀疏存儲方式。

1.? 常規&特殊矩陣形態

常規矩陣形態

采用二維數組來存儲，可按行優先或列優先的形式記錄。

特殊矩陣形態

特殊矩陣指的是具有許多相同元素或零元素，并且這些元素的分布有一定規律性的矩陣。這種矩陣如果還使用常規方式來存儲，就會產生大量的空間浪費，為了節省存儲空間，可以對這類矩陣采用壓縮存儲，壓縮存儲的方式是把那些呈現規律性分布的相同元素只分配一個存儲空間，對零元素不分配存儲空間。

1)? 對稱矩陣

對于矩陣中的任何一個元素都有aij=aji? 1≤i,j≤n這樣的矩陣就叫對稱矩陣。也就是上三角等于下三角。對于對稱矩陣的存儲方式是存儲上三角或者下三角加對角線，假設一個n階對稱方陣，如果全部存儲使用的存儲空間是n*n，壓縮存儲則是n(n+1)/2，對角線元素為n個，除了對角線之外為n*n-n，需要存儲的元素(n*n-n)/2，加上對角線上的元素后結果就是n(n+1)/2。假設存儲一個n階對稱矩陣，使用sa[n(n+1)/2]來存儲，那么sa[k]與ai,j的關系是：

當i>=j時，k= i(i-1)/2+j-1

當i

2)? 三角矩陣

上三角或下三角全為相同元素的矩陣。可用類似于對稱矩陣的方式存儲，再加上一個位置用來存儲上三角或者下三角元素就好。

a[i][j]=a[0][0] + (i* (i+1) /2+j) *size;

size為每個數據所占用的存儲單元大小。

3)? 帶狀對角矩陣

矩陣中所有非0元素集中在主對角線為中心的區域中。下圖為3條對角線區域，其他區域的元素都為0。除了第一行和最后一行僅2個非零元素，其余行都是3個非零元素，所以所需的一維空間大小為：3n - 2；

a[i][j]的內存地址=a00首地址+ ((3 * i -1) + (j-i+1)) * size；(size為每個數據所占用的存儲單元大小)。比如首地址為1000，每個數據占用2個存儲單元，那么a45在內存中的地址=1000+13 * 2=1026；

2.? 稀疏矩陣及壓縮

由于特殊矩陣中非零元素的分布是有規律的，所以總是可以找到矩陣元素與一維數組下標的對應關系，但還有一種矩陣，矩陣中大多數元素都為0，一般情況下非零元素個數只占矩陣元素總數的5%以下，且元素的分布無規律，這樣的矩陣稱為稀疏矩陣。

三元組順序法

如果采用常規方法存儲稀疏矩陣，會相當浪費存儲空間，因此只存儲非零元素。除了存儲非零元素的值之外，還需要同時存儲非零元素的行、列位置，也就是三元組(i,j,aij)。矩陣元素的存儲順序并沒有改變，也是按列的順序進行存儲。

è

三元組也就是一個矩陣，一個二維數組，每一行三個列，分別為行號、列號、元素值。由于三元組在稀疏矩陣與內存地址間扮演了一個中間人的角色，所以稀疏矩陣進行壓縮存儲后，便失去了隨機存取的特性。

行邏輯鏈接的順序表

為了隨機訪問任意一行的非零元，這種方式需要一個數組指向每一行開始元素(非零元素)的位置。這種方式適合矩陣相乘。

十字鏈表法

當矩陣中元素非零元個數和位置在操作過程中變化較大時，就不宜采用順序存儲結構來表示三元組的線性表。如在進行加減操作時，會出現非零元變成零元的情況，因此，就適合用十字鏈表來存儲。

十字鏈表的結構有五個域，一個數據域存放矩陣元，i、j 域分別存放該非零元所在的行、列。還有right、down域，right指向右邊第一個矩陣元的位置，down用來指向下面第一個矩陣元的位置。然后建立兩個數組，分別指向每行/列的第一個元素。十字鏈表在圖中也有應用，用來存儲圖。

八．圖結構存儲

圖通常用來表示和存儲具有“多對多”關系的數據，是數據結構中非常重要的一種結構。

1.? 鄰接矩陣結構

圖的鄰接矩陣存儲方式是用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，一個二維數組（鄰接矩陣）存儲圖中的邊或弧的信息。

設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣，定義為：

無向圖

1）基于鄰接矩陣容易判斷任意兩頂點是否有邊無邊；

2）某個頂點的度就是這個頂點vi在鄰接矩陣中第i行或(第i列)的元素和；

3）vi的所有鄰接點就是矩陣中第i行元素，如arc[i][j]為1就是鄰接點；

n個頂點和e條邊的無向網圖的創建，時間復雜度為O(n + n2 + e)，其中對鄰接矩陣的初始化耗費了O(n2)的時間。

有向圖

有向圖講究入度和出度，頂點vi的入度為1，正好是第i列各數之和。頂點vi的出度為2，即第i行的各數之和。

若圖G是網圖，有n個頂點，則鄰接矩陣是一個n*n的方陣，定義為：

wij表示(vi,vj)上的權值。無窮大表示一個計算機允許的、大于所有邊上權值的值，也就是一個不可能的極限值。

下面左圖是一個有向網圖，右圖是其鄰接矩陣。

2.? 鄰接表結構

鄰接矩陣是不錯的一種圖存儲結構，但對邊數相對頂點較少的圖存在對存儲空間的極大浪費。因此，找到一種數組與鏈表相結合的存儲方法稱為鄰接表。鄰接表的處理方法：

1）圖中頂點用一個一維數組存儲，當然，頂點也可用單鏈表來存儲，不過數組較容易的讀取頂點的信息。

2）圖中每個頂點vi的所有鄰接點構成一個線性表，由于鄰接點的個數不定，所以用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖則稱為頂點vi作為弧尾的出邊表。

例如，下圖就是一個無向圖的鄰接表的結構。

從圖中可以看出，頂點表的各個結點由data和firstedge兩個域表示，data是數據域，存儲頂點的信息，firstedge是指針域，指向邊表的第一個結點，即此頂點的第一個鄰接點。邊表結點由adjvex和next兩個域組成。adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下標，next則存儲指向邊表中下一個結點的指針。

對于帶權值的網圖，可以在邊表結點定義中再增加一個weight的數據域，存儲權值信息即可，如下圖所示。

對于無向圖，一條邊對應都是兩個頂點，所以在循環中，一次就針對i和j分布進行插入。本算法的時間復雜度，對于n個頂點e條邊來說，容易得出是O(n+e)。

3.? 十字鏈表存儲

對于有向圖來說，鄰接表是有缺陷的。關心了出度問題，想了解入度就必須要遍歷整個圖才知道，反之，逆鄰接表解決了入度卻不了解出度情況。而十字鏈表存儲方法可把鄰接表和逆鄰接表結合。

重新定義頂點表結點結構，如下所示

其中firstin表示入邊表頭指針，指向該頂點的入邊表中第一個結點，firstout表示出邊表頭指針，指向該頂點的出邊表中的第一個結點。

重新定義邊表結構，如下所示

其中tailvex是指弧起點在頂點表的下表，headvex是指弧終點在頂點表的下標，headlink是指入邊表指針域，指向終點相同的下一條邊，taillink是指邊表指針域，指向起點相同的下一條邊。還可增加一個weight域來存儲權值。

比如下圖，頂點依然是存入一個一維數組，實線箭頭指針的圖示完全與鄰接表相同。就以頂點v0來說，firstout指向的是出邊表中的第一個結點v3。所以v0邊表結點hearvex=3，而tailvex其實就是當前頂點v0的下標0，由于v0只有一個出邊頂點，所有headlink和taillink都是空的。

虛線箭頭的含義。它其實就是此圖的逆鄰接表的表示。對于v0來說，它有兩個頂點v1和v2的入邊。因此它的firstin指向頂點v1的邊表結點中headvex為0的結點，如上圖圓圈1。接著由入邊結點的headlink指向下一個入邊頂點v2，如上圖圓圈2。對于頂點v1，它有一個入邊頂點v2，所以它的firstin指向頂點v2的邊表結點中headvex為1的結點，如上圖圓圈3。

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在一起，這樣既容易找到以v為尾的弧，也容易找到以v為頭的弧，因而較易求得頂點的出度和入度。除了結構復雜一點外，其實創建圖算法的時間復雜度和鄰接表相同，因此在有向圖應用中，十字鏈表是非常好的數據結構模型。

九．分布式圖存儲

分布式圖(巨型圖)的存儲總體上有邊分割和點分割兩種方式，目前業界廣泛接受并使用的存儲方式為點分割，點分割在處理性能上要高于邊分割。

l? 邊分割（Edge-Cut）：每個頂點都存儲一次，但有的邊會被打斷分到兩臺機器上。這樣做的好處是節省存儲空間；壞處是對圖進行基于邊的計算時，對于一條兩個頂點被分到不同機器上的邊來說，要跨機器通信傳輸數據，內網通信流量大。

l? 點分割（Vertex-Cut）：每條邊只存儲一次，都只會出現在一臺機器上。鄰居多的點會被復制到多臺機器上，增加了存儲開銷，同時會引發數據同步問題。好處是可以大幅減少內網通信量。

雖然兩種方法互有利弊，但現在是點分割占上風，各種分布式圖計算框架都將自己底層的存儲形式變成了點分割。主要原因有以下兩個。

1)? ?磁盤價格下降，存儲空間不再是問題，而內網通信資源無突破性進展，集群計算時內網帶寬是寶貴的，時間比磁盤更珍貴。這點類似于常見的空間換時間的策略。

2)? ?在當前應用場景中，絕大多數網絡都是“無尺度網絡”，遵循冪律分布，不同點的鄰居數量相差非常懸殊。而邊分割會使那些多鄰居的點所相連的邊大多數被分到不同的機器上，這樣的數據分布會使得內網帶寬更加捉襟見肘，于是邊分割存儲方式被漸漸拋棄。

1.? GraphX存儲模式

借鑒PowerGraph,使用點分割方式存儲圖,用三個RDD(Resilient Distributed Dataset,彈性分布式數據集)存儲圖數據信息：

VertexTable(id, data): id為Vertex id，data為Edge data

EdgeTable(pid, src, dst, data):pid為PartionId，src為原頂點id，dst為目的頂點id

RoutingTable(id, pid)：id為Vertex id，pid為Partion id

點分割存儲實現如下圖所示：

2.? 超大規模圖存儲

超大規模圖（數十億點，數百億邊）存儲，需要分布式的存儲架構。在圖加載時，整張圖在圖處理引擎內部被切分為多個子圖，每個計算節點被分配1個或幾個子圖進行加載。

一張有向圖的基本元素是頂點和邊,一般都具有類型和權重，邊是有向的，一條邊由：起點、終點、類型三者標識，即相同的兩點之間可以同時具有多條不同類型的邊。下面是一個簡單的帶權異構屬性圖示例：

頂點以uint64標識，頂點類型、邊類型，以及點邊上的三種屬性均采用字符串描述。對于例子中的圖，需要將點邊歸類編號，得到一張可以識別的圖。

圖數據JSON格式

JSON文件由兩大部分組成，點和邊，分別存儲在JSON對象的“nodes”、“edges”中。每個節點對象包含了節點的id，type，weight以及name，type和value屬性信息字段。每個邊對象則包含這個邊相關聯的起點和終點id：src和dst，和邊相關的屬性信息。

點和邊屬性索引

·? ? ?全局hash索引：全局采樣過濾精確匹配某種屬性的點和邊。適用于全局采樣負例的時候，加上過濾條件，只采樣滿足條件的負例。支持的查詢有：eq，not_eq，in，not_in。

·? ? ?全局range索引：全局采樣過濾某種屬性在某個范圍內的點和邊。適用于全局采樣負例時，加上過濾條件采樣滿足條件的負例。支持：eq，not_eq，ge，le，gt，lt，in，not_in

·? ? ?鄰居索引： 采樣某個點的滿足某種屬性的鄰居節點。適用于鄰居采樣的時候，加上過濾條件，只采樣滿足條件的鄰居節點。支持的查詢與全局range索引相同。

圖數據二進制生成

將JSON文件轉化為分布式圖引擎加載所需要的二進制格式，包括分片個數等。

… 廣告搜索場景：圖嵌入，向量化最近鄰檢索網絡結構

… …

最 后

當今的計算機以運算器為中心，I/O設備與存儲器間的數據傳送都要經過運算器。相對處理器的速度來說，IO設備就慢多了。就SSD來說，IO也是遠低于RAM的讀寫速率。IO讀寫的耗時常常成為性能的瓶頸點，所以要減少IO次數，且隨著數據量增加，IO次數穩定是數據存儲引擎的核心要務。當然了，CPU等指標也是很重要的。

文中倒排索引存儲章節介紹了Lucene如何實現倒排索引的關鍵技術，如何精打細算每一塊內存、磁盤空間、如何用詭譎的位運算加快處理速度，但往高處思考，再類比一下MySql就會發現，雖然都是索引，但實現機制卻截然不同。

很多業務、技術上要解決的問題，大都可以抽象為一道算法題，復雜問題簡單化。每種數據存儲引擎都有自己要解決的問題（或者說擅長的領域），對應的就有自己的數據結構，而不同的使用場景和數據結構，需要引入不同的索引，才能起到最大化加快查詢、檢索的目的。

… ……

數據結構 MySQL 存儲

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。