概念

• 查找表: 同一類型的數(shù)據(jù)元素( 或記錄 ) 構(gòu)成的集合;

• 關(guān)鍵字: 數(shù)據(jù)元素中各個數(shù)據(jù)項的值, 又稱鍵值;

• 主關(guān)鍵: 唯一標識一個記錄的關(guān)鍵字;

• 次關(guān)鍵字: 可以識別多個記錄的關(guān)鍵字;
  <img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/search-concept-1.png" width="568" />

• 查找: 給定某個值,在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素(或記錄);

• 查找表按著操作分為靜態(tài)查找表和動態(tài)查找表

• 靜態(tài)查找表: 只做查找操作;
• 動態(tài)查找表: 在查找過程中同事對數(shù)據(jù)進行操作( 新增,修改或刪除 );

• 面對查找要還有結(jié)構(gòu), 對于不用的羅輯需要做不同的結(jié)構(gòu),比如:線性表,樹等等.

順序查找(線性查找)

按著順序從前到后或從后到前逐個查找, 時間復(fù)雜度是O(n),

完整代碼地址

有序查找

二分查找( 拆半查找 ), 時間復(fù)雜度為 O(logn);

完整代碼地址

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/search-binary-1.png" width="558" />

插值查找

• 將二分查找的 mid = （low+high）/ 2, 即 mid = low + 1/2 * (high - low);
• 插值查找將 以上的1/2變?yōu)?(key - a[low]) / (a[high] - a[low])
• 即: mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)
• 根據(jù)關(guān)鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了比較次數(shù);
• 適合于分布均勻的有序查找;

斐波那契查找 ( 黃金比例查找 )

• 黃金比例又稱黃金分割，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1
• 斐波那契數(shù)列 F(n) = F(n-1)+F(n-1);
  • 1 1 2 3 5 8 13 21 34 55 89 ....
  • 5/8=0.625, 8/13=0.615,13/21=0.619, 55/89=0.618...
  • 隨著斐波那契數(shù)列的遞增，前后兩個數(shù)的比值會越來越接近0.618，利用這個特性，我們就可以將黃金比例運用到查找技術(shù)中.
• 黃金分割的原理來確定mid的位置: mid = low+F[k-1]-1;

完整代碼地址

分析以上三種有序查找方式的分割點 mid

1. 拆半查找： mid = (low+high)/2, 加法與除法運算；
2. 插值查找： mid = low+(high-low)*(key-a[low])/(a[hign]-a[low])，復(fù)雜的四則運算；
3. 斐波那契查找： mid = low+F[k-1]-1; 只有減法運算；

比較以上三種有序查找，查找的時間復(fù)雜度都是log(n)，但是在海量數(shù)據(jù)的查找過程中，性能上斐波那契查找是最優(yōu)秀的；

線性索引查找

索引定義： 把一個關(guān)鍵字與它對應(yīng)的記錄相關(guān)聯(lián)的過程；
索引技術(shù)： 是組織大型數(shù)據(jù)以及磁盤文件的一種重要技術(shù)；
一個索引由若干個索引項組成，一個索引項至少包含關(guān)鍵字和對應(yīng)的記錄在存儲器中的地址；

**索引分類,按著結(jié)構(gòu)分為：線性索引，樹形索引，多級索引； **

• 線性索引： 將索引項集合組織為線性結(jié)構(gòu)（也稱索引表），分為以下三種：

* 稠密索引
* 分塊索引
* 倒排索引

稠密索引

• 索引項數(shù)量 = 數(shù)據(jù)記錄數(shù)量；
• 索引表按著關(guān)鍵碼有序排列，可以對索引表使用拆半、插值、斐波那契等有序查找找到要查找記錄的地址，然后根據(jù)指針地址找到對應(yīng)的真實數(shù)據(jù)記錄；
• 適合數(shù)據(jù)量小的情況;
• 下圖：左側(cè)代表索引表，右側(cè)代表真實記錄；
  <img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/line-dense-index.png" width="" />

分塊索引

• 索引項數(shù)量<數(shù)據(jù)記錄數(shù)量, 所以索引表占用內(nèi)存資源小;
• 將數(shù)據(jù)集分塊, 塊間有序, 比如: 第二塊所有記錄的關(guān)鍵字均大于第一塊中所有記錄的關(guān)鍵字, 第三塊大于第二塊;
• 分塊索引: 對于分塊有序的數(shù)據(jù)集,將每塊對應(yīng)一個索引項;
• 比順序查找O(n)快，比二分O(logn)慢;
• 索引項結(jié)構(gòu):

• 最大關(guān)鍵碼(數(shù)據(jù)記錄中每塊的最大關(guān)鍵字)
• 塊中的記錄總數(shù)

• 指向塊首數(shù)據(jù)元素的指針

  
  
  

倒排索引

• 由屬性（字段、關(guān)鍵字）的值確定記錄的位置。
• 索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址
• 優(yōu)點：查找記錄快
• 缺點：記錄號不定長, 新增/修改/刪除操作時維護成本較大;
• 例如：通過文章中的單詞找到對應(yīng)的文章;
  • 文章1： it is what it is
  • 文章2：what is it
  • 文章3：it is a banana

以上查找方式都是靜態(tài)查找, 特別是有序查找對于新增/修改/刪除操作復(fù)雜, 所以就有了以下的動態(tài)查找;

動態(tài)查找

• 概念: 在查找的過程對數(shù)據(jù)進行新增/修改/刪除等操作;
• 二叉排序樹-BST:

https://github.com/liangxifeng833/my_program/blob/master/datastruct/%E6%9F%A5%E6%89%BE-%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91-BST.md

• 平衡二叉樹-AVL

https://github.com/liangxifeng833/my_program/blob/master/datastruct/%E6%9F%A5%E6%89%BE-%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91-AVL.md

• 多路查找樹-B樹

https://github.com/liangxifeng833/my_program/blob/master/datastruct/%E6%9F%A5%E6%89%BE-%E5%A4%9A%E8%B7%AF%E6%9F%A5%E6%89%BEB%E6%A0%91.md