數據存取路徑

數據存取是指資料庫數據存貯組織和存貯路徑的實現和維護。在計算機中，數據一般以檔案形式保存或存放在資料庫中。在資料庫，數據存取路徑分為主存取路徑與輔存取路徑，前者主要用於主鍵檢索，後者用於輔助鍵檢索。在系統中，路徑一般分為相對路徑和絕對路徑。

基本介紹

• 中文名：數據存取路徑
• 外文名：Data access path
• 學科：計算機
• 定義：存取數據的位置
• 有關術語：主存取路徑、輔存取路徑
• 領域：資料庫系統

簡介

數據存取路徑是指存取數據的位置，由於程式運行具有局部性，不可能把所有數據都調入記憶體，在記憶體中只有一部分數據，其餘數據都在外存，因此數據存取路徑分為輔存存取路徑和記憶體存取路徑，不同的路徑，查找的方法是不同的，一般分為記憶體查找和輔存查找。

路徑名

在樹形目錄結構中，從根目錄到任何數據檔案，都只有一條惟一的通路。在該路徑上從樹的根(即主目錄)開始，把全部目錄檔案名稱與數據檔案名稱依次地用“/”連線起來，即構成該數據檔案的路徑名(path name)。系統中的每一個檔案都有惟一的路徑名。

相對路徑

當一個檔案系統含有許多級時，每訪問一個檔案，都要使用從樹根開始直到樹葉(數據檔案)為止的、包括各中間節點(目錄)名的全路徑名。這是相當麻煩的事，同時由於一個進程運行時所訪問的檔案大多僅局限於某個範圍，因而非常不便。基於這一點，可為每個進程設定一個“當前目錄” ，又稱為“工作目錄” 。進程對各檔案的訪問都相對於“當前目錄”。而進行。此時各檔案所使用的路徑名，只需從當前目錄開始，逐級經過中間的目錄檔案，最後到達要訪問的數據檔案。把這一路徑上的全部目錄檔案名稱與數據檔案名稱用“/”連線形成路徑名。如用戶 B 的當前目錄是 F，則此時檔案 J 的相對路徑名僅是 J 本身。這樣，把從當前目錄開始直到數據檔案為止所構成的路徑名，稱為相對路徑名(relative path name)。

絕對路徑

絕對路徑是指目錄下的絕對位置，直接到達目標位置，通常是從盤符開始的路徑。

完整的描述檔案位置的路徑就是絕對路徑，以web站點根目錄為參考基礎的目錄路徑。絕對路徑名的指定是從樹型目錄結構頂部的根目錄開始到某個目錄或檔案的路徑，由一系列連續的目錄組成，中間用斜線分隔，直到要指定的目錄或檔案，路徑中的最後一個名稱即為要指向的目錄或檔案。之所以稱為絕對，意指當所有網頁引用同一個檔案時，所使用的路徑都是一樣的。

記憶體查找方法

順序查找

順序查找(sequential scarch)又稱線性查找，是‘種最簡單的查找方法。它是指將數據以線性表的形式存儲，用線性表來表示靜態查找表。其基本思想是：從線性表中第一個記錄開始，依次比較每個數據元素的關鍵字，若記錄的關鍵字與給定值相等，則查找成功返回該元素序號；若查完整個線性表都沒有與給定值匹配的元素，則查找失敗。

複雜度分析：

查找成功時的平均查找長度為：（假設每個數據元素的機率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

當查找不成功時，需要n+1次比較，時間複雜度為O(n);

所以，順序查找的時間複雜度為O(n)。

折半查找

二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

複雜度分析：最壞情況下，關鍵字比較次數為log2(n+1)，且期望時間複雜度為O(log2n)；

斐波那契查找

基本思想：也是二分查找的一種提升算法，通過運用黃金比例的概念在數列中選擇查找點進行查找，提高查找效率。同樣地，斐波那契查找也屬於一種有序查找算法。

相對於折半查找，一般將待比較的key值與第mid=（low+high）/2位置的元素比較，比較結果分三種情況：

1）相等，mid位置的元素即為所求

2）>，low=mid+1;

3）<，high=mid-1。

斐波那契查找與折半查找很相似，他是根據斐波那契序列的特點對有序表進行分割的。他要求開始表中記錄的個數為某個斐波那契數小1，及n=F(k)-1;

開始將k值與第F(k-1)位置的記錄進行比較(及mid=low+F(k-1)-1),比較結果也分為三種

1）相等，mid位置的元素即為所求

2）>，low=mid+1,k-=2;

說明：low=mid+1說明待查找的元素在[mid+1,high]範圍內，k-=2 說明範圍[mid+1,high]內的元素個數為n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個，所以可以遞歸的套用斐波那契查找。

3）<，high=mid-1,k-=1。

說明：low=mid+1說明待查找的元素在[low,mid-1]範圍內，k-=1 說明範圍[low,mid-1]內的元素個數為F(k-1)-1個，所以可以遞歸 的套用斐波那契查找。

複雜度分析：最壞情況下，時間複雜度為O(log2n)，且其期望複雜度也為O(log2n)。

二叉樹查找算法

基本思想：二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小於右分支的值，然後在就行和每個節點的父節點比較大小，查找最適合的範圍。這個算法的查找效率很高，但是如果使用這種查找方法要首先創建樹。

二叉查找樹（BinarySearch Tree，也叫二叉搜尋樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

1）若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

2）若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

3）任意節點的左、右子樹也分別為二叉查找樹。

輔存查找方法

B樹和B+樹（B Tree/B+Tree）

平衡查找樹中的2-3樹以及其實現紅黑樹。2-3樹種，一個節點最多有2個key，而紅黑樹則使用染色的方式來標識這兩個key。

數據結構對B樹的定義為“在計算機科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序並允許以O(log n)的時間複雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多於2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B樹為系統最最佳化大塊數據的讀和寫操作。B-tree算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在資料庫和檔案系統。

B樹定義：

B樹可以看作是對2-3查找樹的一種擴展，即他允許每個節點有M-1個子節點。

·根節點至少有兩個子節點

·每個節點有M-1個key，並且以升序排列

·位於M-1和M key的子節點的值位於M-1 和M key對應的Value之間

·其它節點至少有M/2個子節點

B+樹定義：

B+樹是對B樹的一種變形樹，它與B樹的差異在於：

• 有k個子結點的結點必然有k個關鍵碼；
• 非葉結點僅具有索引作用，跟記錄有關的信息均存放在葉結點中。
• 樹的所有葉結點構成一個有序鍊表，可以按照關鍵碼排序的次序遍歷全部記錄。

分塊查找

分塊查找又稱索引順序查找，它是順序查找的一種改進方法。
算法思想：將n個數據元素"按塊有序"劃分為m塊（m ≤ n）。每一塊中的結點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素，……
算法流程：
step1 先選取各塊中的最大關鍵字構成一個索引表；
step2 查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；然後，在已確定的塊中用順序法進行查找。

散列查找

哈希函式的規則是：通過某種轉換關係，使關鍵字適度的分散到指定大小的的順序結構中，越分散，則以後查找的時間複雜度越小，空間複雜度越高。

算法流程：

1）用給定的哈希函式構造哈希表；

2）根據選擇的衝突處理方法解決地址衝突；

常見的解決衝突的方法：拉鏈法和線性探測法。

3）在哈希表的基礎上執行哈希查找。

哈希表是一個在時間和空間上做出權衡的經典例子。如果沒有記憶體限制，那么可以直接將鍵作為數組的索引。那么所有的查找時間複雜度為O(1)；如果沒有時間限制，那么我們可以使用無序數組並進行順序查找，這樣只需要很少的記憶體。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調整哈希函式算法即可在時間和空間上做出取捨。

在外部查找中，查找的數據規模一般很大，為了提高查找效率與速度，一般採用散列查找，分塊查找，B/B+樹查找。