T-SQL筆記3_索引觀念和 B-Tree(SQL))

T-SQL筆記3_索引觀念和 B-Tree(SQL))_Performance Tuning技巧

- 1月 13, 2019

想想當我們以前在使用國語辭典時若不透過部首、筆劃來查對應出現頁數時
此時一定是從第一頁慢慢翻直到找到目標為止
因此索引在日常生活中很常用到

包括以前常見的電話簿用姓名筆劃、住址來排
書本前面的章節用字母來排序等等

結構化查詢一般的運作
採用 Full-Scan 機制 或 循序搜尋(Sequential Search) -->未先排序
也就是
當你要在一萬筆資料群的資料表中查找到特定匹配條件的
單筆或多筆資料時
會從頭掃描整張表一遍直到查詢到目標為止。
想當然這種查詢是十分沒有效率的!!

所以在資料結構應用上使用不同演算做法
會有不同回饋!!!

舉例: 同樣一組數據序列用不同查詢下所產生的比對次數就有明顯的差異
循序(線性)查詢

非循序(非線性)查詢 E.g. 二元(分/岔)

資料庫之索引

這裡我們拿一本書最後頭的索引
來做一個生活例子比擬
你會看到一些常看或市面上書籍
後面都會有依照可能是英文字母開頭做排序的
以中文字典的部分則可能是用部首、注音、筆畫去做查詢索引

https://www.prismnet.com/~hcexres/textbook/indexing.html

http://gimilee.pixnet.net/blog/post/209620930-大推薦－全方位造詞造句大詞典

藉由 Index 我們可以更快速找到我們想要的目標開頭為X的字眼

在SQL Server這部分是採用 B-Tree(B型束狀結構)
B樹(B-Tree) 在你瞭解這個名詞前
可能需要先有關於樹的一些先備知識

Tree資料結構專術語(行話)介紹:

1.節點(Node):每一項data(資料值) -->A ,B ,C......,L
2.樹根(Root):每一棵樹最上層之節點 --> A
3.子樹(Sub Tree):去除樹根(A)後 , 所剩之以B、C、D為樹根之三棵樹也就是「子樹」

4.邊(Edge):節點之間的連線。
5.樹葉(Leaf):下方無串接任一節點(最末端)。換言之，就是分支度為0的節點，又稱終端節點。
6.樹林(Forest):去除樹根後剩餘的部分(三個子樹)即「樹林」
7.階度(Level):節點所位在之層級位置，如下 D 對應之Level即2
8.高度(Height):一座樹(從Root起算)之最大階度(階度累積總層個數) ，如下即:4
9.父節點(Parent):B是E和F的父節點， E是K的父節點 (相對的!!!)
10.子節點(Children):E和F是B的子節點(相對的!!!)
11.分支度(Degree):一個節點的子樹個數如下Degree(A)=3 , Degree(B)=2

位於樹所有Node中分支度最大方就可被稱為此樹的樹的分支度(degree of a tree)

各個節點串有幾個子樹則為節點的分支度(degree of a node)

樹狀結構是由一個或多個節點組合而成的有限集合，必須要滿足三點：
1. Tree(樹)不可以為空集合，至少有一個節點稱為Root(根節點)。
2. 其餘的節點分成T1 , T2,.....,Tn個互斥集合。
因此，我們也可以稱T1 , T2,....., Tn 為根節點的子樹 ( Sub tree ) 。

3.樹狀結構中不可以含有重邊、迴圈或不相連的情況。

4.樹的非終端節點分支度不可為0

N元樹

二元樹 : 分兩岔

三元樹: 分三岔

二元樹

1.最多兩個子樹(節點):左子樹/右子樹

2.可以是空集合

3.節點分支度: 0<=d<=2

4.具有順序(依據左右節點:分前、中、後)

可用陣列、鏈結串列實作

【節點之插入】

先插入的作為樹根

後續插入的新節點，若小於樹根則移往左側直到抵達子樹末端(變為樹葉)

反之則移右側

在資料庫的一些學科當中會去探討到
Index的種類(主要以索引結構來表達資料之間的順序關係)
又會依照層級區分為
1.單層索引 : 會依照有序的索引欄位去建立一個額外的索引表
例如:主索引(primary index)、次索引(secondary index)、叢集索引(clustering index)
、ISAM file...etc

IBM 曾提出
ISAM file(Indexed Seguential Access Method) /索引順序存取方法
和硬體有關(磁柱、磁軌)，屬於靜態多層索引(固定三層)

備註:
密集索引:是指每筆record皆會有一相對的index
非密集索引:並非每筆record皆會有一相對的index

1-1.主索引(primary index):以主鍵作為索引欄位屬於非密集索引(non-dense)。
主要會依照主鍵值排序，但索引表項目只會有資料檔主鍵部分的鍵值。
索引記錄筆數即為資料檔案區塊(data block)數目。

1-2.次索引(secondary index):其索引欄位則使用次鍵值or非鍵值來作為索引欄位
當使用次鍵值作為索引時則屬於密集索引(record不會重複)
此時的索引紀錄數就視為資料記錄筆數

當使用非鍵值作為索引時則屬於非密集索引(record有可能重複)
索引記錄數則視為相異索引欄位數
此時每筆record不僅不會排序且紀錄也會有機會重複
萬一多筆紀錄都含有相同key值，導致一個block無法負荷所有紀錄pointer通常會
被用Linklist來設計多個block串連。

1-3.叢集索引(clustering index)
是以非鍵值作為索引欄位，資料是會被排序的。屬於非密集索引，因為叢集欄位可能有機會多筆紀錄皆相同值，因此非每筆紀錄都有一筆索引項。
索引記錄數則視為相異索引欄位數(不同叢集欄位總數)

2.多層索引: 則是以樹狀結構來建立索引，比方說
B-tree、B+ tree 、VSAM file...etc

IBM 曾提出
VSAM file(Virtual Storage Access Method) / 虛擬存儲存取方法
和硬體無相關，屬於動態多層索引，類似書本、電話簿、字典的索引

B-tree:
每一個節點視為磁碟中一個區塊。
當分支度為p時其節點結構如下