資料庫自動分配演算法

1. 什麼是基於索引搜索 動態分配演算法

倒排索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件。建立全文索引中有兩項非常重要，一個是如何對文本進行分詞，一是建立索引的數據結構。分詞的方法基本上是二元分詞法、最大匹配法和統計方法。索引的數據結構基本上採用倒排索引的結構。
分詞的好壞關繫到查詢的准確程度和生成的索引的大小。在中文分詞發展中，早期經常使用分詞方式是二元分詞法，該方法的基本原理是將包含中文的句子進行二元分割，不考慮單詞含義，只對二元單詞進行索引。因此該方法所分出的單詞數量較多，從而產生的索引數量巨大，查詢中會將無用的數據檢索出來，好處是演算法簡單不會漏掉檢索的數據。之後又發展出最大匹配分詞方法，該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似，對常用單詞生成一個詞典，分析句子的過程中最大的匹配字典中的單詞，從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產生錯誤，比如「首飾和服裝」會將「和服」作為單詞分出。達夢資料庫採用的是改進的逆向最大分詞方法，該分詞方法較正向正確率有所提高。最為復雜的是通過統計方式進行分詞的方法。該方法採用隱式馬爾科夫鏈，也就是後一個單詞出現的概率依靠於前一個單詞出現的概率，最後統計所有單詞出現的概率的最大為分詞的依據。這個方法對新名詞和地名的識別要遠遠高於最大匹配法，准確度隨著取樣文本的數量的增大而提高。
二元分詞方法和統計方法是不依賴於詞典的，而最大匹配法分詞方法是依賴於詞典的，詞典的內容決定分詞結構的好壞。
全文檢索的索引被稱為倒排索引，之所以成為倒排索引，是因為將每一個單詞作為索引項，根據該索引項查找包含該單詞的文本。因此，索引都是單詞和唯一記錄文本的標示是一對多的關系。將索引單詞排序，根據排序後的單詞定位包含該單詞的文本。
步驟1）讀取一整條句子到變數str中，轉到步驟2

步驟2）從句子的尾端讀取1個字到變數word中，轉到步驟3

步驟3）在字典查找word中保存的單詞。如果存在則保存word，轉到步驟4，否則轉到步驟5）

步驟4）如果是字典中最大單詞或者超過最大單詞數（認定為新詞），從句尾去掉該單詞，返回步驟2

步驟5）讀取前一個字到word中，構成新單詞，轉到步驟3）

詞庫的內存數據結構和詞庫中單詞的匹配演算法

內存中單詞採用層次結構保存

2. 資料庫分庫分表（二）Twitter-Snowflake（64位分布式ID演算法）分析與JAVA實現

Twitter-Snowflake演算法產生的背景相當簡單，為了滿足Twitter每秒上萬條消息的請求，每條消息都必須分配一條唯一的id，這些id還需要一些大致的順序（方便客戶端排序），並灶核且在掘頃分布式系統中不同機器產生的id必須不同。各種主鍵ID生成策略對比，見 常見分布式主鍵ID生成策略

把 41位的時間前綴 ， 10位的節點標識 ， 12位的sequence 組合在一起。
除了最高位bit標記為不可用以外，其餘三組bit佔位均可浮動，看具體的業務需求而定。 默認情況下41bit的時間戳，1970年算起可以支持該演算法使用到2038年，10bit的工作機器id可以支持1024台機器，序列號支持1毫秒產生4096個自增序列id 。

Snowflake是Twitter在2010年用Scala語言寫的一套主鍵生成策略，用Thrift對外發布主鍵生成服務，其中依賴了Twitter內部的Infrastructure，後來Twitter用 Twitter-server 代替了Snowflake，自2012年起就未更新。見 Twitter-Snowflake項目地址（Tags:snowflake-2010）
之前寫了一個Java的實現，改自網上一個版本: Twitter的分布式自增ID演算法Snowflake實現分析及其Java、Php和Python版 。後來看到當當網的 Sharding-JDBC 分庫分表中間件已實現了此演算法。就直接在其中添隱散掘加了一些新特性，已merge。( 具體實現 , 說明文檔 )
添加3種IdGenerator實現。

用筆記本（i7-3632QM 2.2GHz 四核八線程）測試了下，每秒生成409萬（理論上的峰值），CPU佔用率18.5%。

3. 資料庫技術知識數據結構的演算法

資料庫技術知識數據結構的演算法

對於將要參加計算機等級考試的考生來說，計算機等級考試的知識點輔導是非常重要的復習資料。以下是我收集的資料庫技術知識數據結構的演算法，希望大家認真閱讀!

1、數據：數據的基本單位是數據元素。數據元素可由一個或多個數據項組成。數據項是數據的不可分割的最小單位

2、數據結構：數據的邏輯結構、數據的存儲結構、數據的運算

3、主要的數據存儲方式：順序存儲結構(邏輯和物理相鄰，存儲密度大)和鏈式存儲結構

順序存儲結構：

順序存儲計算公式 Li=L0+(i-1)×K 順序結構可以進行隨機存取;插人、刪除運算會引起相應節點的大量移動

鏈式存儲結構：a、指針域可以有多個，可以指向空，比比順序存儲結構的存儲密度小

b、邏輯上相鄰的節點物理上不一定相鄰。 c、插人、刪除等不需要大量移動節點

4、順序表：一般情況下，若長度為n的順序表，在任何位置插入或刪除的概率相等，元素移動的平均次數為n/2(插入)和(n-1)/2(刪除)。

5、鏈表：線性鏈表(單鏈表和雙向鏈表等等)和非線性鏈表

線性鏈表也稱為單鏈表，其每個一節點中只包含一個指針域，雙鏈表中，每個節點中設置有兩個指針域。(注意結點的插入和刪除操作)

6、棧：“後進先出”(LIFO)表。棧的應用：表達式求解、二叉樹對稱序周遊、快速排序演算法、遞歸過程的實現等

7、隊列：“先進先出”線性表。應用：樹的層次遍歷

8、串：由零個或多個字元組成的有限序列。

9、多維數組的順序存儲：

10、稀疏矩陣的存儲：下三角矩陣順序存儲

其他常見的存儲方法還有三元組法和十字鏈表法

11、廣義表：由零個或多個單元素或子表所組成的有限序列。廣義表的元素可以是子表，而子表的元素還可以是子表

12、樹型結構：非線性結構。常用的樹型結構有樹和二叉樹。

二叉樹與樹的區別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區別是：二叉樹的節點的子樹要區分左子樹和右子樹，即使在節點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。

13、樹(森林)與二叉樹之間的轉換(要會轉換)

14、二叉樹和樹的周遊(遍歷)

二叉樹的周遊主要有以下3種方式：前序法(NLR)、對稱序法(LNR)、後序法(LRN)

周遊樹和樹林：深度優先和按廣度優先兩種方式進行。深度優先方式又可分為按先根次序和按後根次序周遊

樹與二叉樹周遊之間的對應關系：按先根次序周遊樹正好與按前序法周遊樹對應的二叉樹等同，後根次序周遊樹正好與按對稱序法周遊對應的`二叉樹等同

按廣度優先方式就是層次次序周遊

15、二叉樹的存儲和線索

二叉樹的存儲結構：二叉樹的llink一rlink法存儲表示

線索二叉樹：在有n個節點的二叉樹的且llink - rlink法存儲表示中，必定有n+1個空指針域

16、哈夫曼樹：一類帶權路徑長度最短的樹。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和WPL。

17、查找：

(1)順序查找：平均查找長度為(n +1 )/2次，時間復雜度為O(n)

(2)二分法查找：線性表節點必須按關鍵碼值排序，且線性表是以順序存儲方式存儲的。查找成功比較次數log2n，查找失敗比較次數log2n+1

(3)分塊查找：先是塊間查找，然後塊內查找。

(4)散列表(哈希表Hash)的存儲和查找：處理沖突的方法：開地址法(線性探測法)、拉鏈法等

負載因子(裝填因子)=表實際存儲的結點個數/表的最大能存儲結點個數(即表長)

二叉排序樹：每個結點左子樹的所有關鍵碼值都小於該結點關鍵碼值，右子樹所有結點關鍵碼值都大於該結點關鍵碼值。對稱周遊二叉排序樹，得到一個有序序列，時間復雜度O(log2n)

B樹和B+樹：M階樹，每個結點至多有M-1個關鍵碼，至少有M/2(取上界)-1個關鍵碼。B樹適合隨機查找，不適合順序查找。B+樹適合順序查找。

18、排序

直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序演算法要了解。

直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序，其他排序為穩定排序