【SQL】EP1：為什麼主鍵Primary Key可使query速度提升? 索引Index到底做了什麼事?

tags: SQL

Primary Key

• 主索引鍵 (PK)
• 系統會同時自動建立一個相對應叢集索引
  
• index
  

Index 索引

• 用空間換取時間

未索引 O(n)	索引 O(log n)

B-Tree

• B：balance
  • 每一個 leaf 到 root 都是一樣的高度 → 保持資料有序
  • select * from student where studentID ='1' 或 select * from student where stuentID='100' ，在 index 上所花的成本都是一樣的
  • 所有 data pointer 都是在 leaf 的地方
• 優點
  • single value search
  • scan a range
  • pattern matching
    • 例如：用 LIKE 進行 prefix pattern matching 查詢
    • LIKE '%AN%'

• B+ Tree
  • leaf 之間再加上一個 pointer
  • 找到資料後，很快地再移到下一個資料而不需要每次都從 root 出發

Hash

• 優點
  • querying for equality
  • 沒有順序 → key-value
  • single value search 比B-Tree快
• 缺點
  • 無法支援有範圍的尋找

• 比較
  
  

其他索引方式

• full-index
• R-Tree

資料庫索引

	PostgreSQL	MySQL	MongoDB
default	B-Tree	B-Tree (根據Storage Engine不同，可能不同)	B-Tree
方式	btree, hash, gist, and gin	HASH, BTREE	B-Tree, Compound, Hash…

Cluster 叢集

	Clustered Index	Nonclustered Index
說明	根據某個資料在儲存空間上排列的順序	不一定要按照實體的資料排列順序
number	唯一	多個
speed	快	慢
額外空間	不需要	需要
CUD成本	實體的儲存順序就是Index上資料的順序，要變動比較麻煩	只要改 pointer 指到新的 page

• 但特定情況，scan還是比較好
  • 當總資料越多或過於破碎，scan時間成本越高
  • 當搜尋結果佔總資料(10%以上)一定比例
    

延伸閱讀

• B-Trees 圖解
• INDEXING
• 資料結構&演算法筆記

Reference 參考資料

• http://vito-note.blogspot.com/2013/05/blog-post_5510.html
• 42 資料庫基礎 - Index 所用的資料結構 B tree
• 47 資料庫基礎 - 以 Hash 為基礎的 Index
• B-Tree Indexes
• 33 資料庫基礎 - 什麼是 Index
• 37 資料庫基礎 - Clustered Index 與 Non-clustered Index

• 資料庫的Index
  • Primary Key
  • Index 索引
    • B-Tree
    • Hash
    • 其他索引方式
  • 資料庫索引
  • Cluster 叢集
  • 延伸閱讀
  • Reference 參考資料
Expand allBack to topGo to bottom

• 資料庫的Index
  • Primary Key
  • Index 索引
    • B-Tree
    • Hash
    • 其他索引方式
  • 資料庫索引
  • Cluster 叢集
  • 延伸閱讀
  • Reference 參考資料