B-Tree와 DB index

• index: DB에서 데이터를 찾을 때 full scan 말고, index를 사용하여 빠르게 한번에 접근할 수 있다
• page: 디스크와 메모리에 데이터를 읽고 쓰는 최소 작업 단위
  • = 한 번 읽을 때 page만큼을 읽어옴

index와 B-Tree

https://mangkyu.tistory.com/286

인덱스 자체가 B-Tree로 구성되어 있다.]

루트 노드에서 찾을 인덱스 키가 어딨는지 page단위로 이동하며 찾는다.

DB에서 BST대신 BTree를 쓰는 이유

• 여러 키를 하나의 노드에 저장하기 때문에 노드 수가 적어 더 적은 디스크 I/O를 발생 시킨다
  
  • 디스크 I/O란, 한 지점에서 다른 지점으로 점프, 위치를 찾아가는 것
  • DB 성능 개선 혹은 쿼리 튜닝은 디스크 I/O 자체를 줄이는 것이 핵심인 경우가 많다
• 자기가 알아서 균형을 맞추기 때문에, 각 데이터 별로 접근 시간이 거의 동일하다.

 

Clustering Index vs. Non-Clustering Index

• Clustering Index: Index Page + Data Page(Leaf node)가 한 곳에 같이 있는 것
  • 모여서(clustered) 이미 정렬되어있음
    • 조회에 유리
    • 삽입엔 불리(정렬 상태를 유지해야 하므로)
  • 정렬하는 기준(보통 PK를 씀)이 존재하므로, 테이블 당 1개만 존재함

https://www.geekphilip.com/2013/06/14/clustered-indexes-vs-non-clustered-indexes/

• Non-Clustering Index: Index Page / Data Page가 따로 있는 것,
  • Index Page의 Leaf node는 Data Page로 가는 포인터를 젖아함
  • 따로 있으므로
    • 조회에 불리
    • 삽입에 유리
  • 테이블 당 여러 개 가능
    • ex. id, name, age 등 다양한 col을 index로 저장해놓을 수 있음

https://www.geekphilip.com/2013/06/14/clustered-indexes-vs-non-clustered-indexes/

 

---

참고

https://mangkyu.tistory.com/286 [MangKyu's Diary:티스토리] 

https://www.geekphilip.com/2013/06/14/clustered-indexes-vs-non-clustered-indexes/