[2023-08-11] Intro to Database Systems 8강 - B+Tree Index

[jonyejin]

📌 개요

• 시간: 2023-08-11(금) 22:00
• 자료: 8강 B+Tree Indexes
• 참여자: 펭귄, 그루트, 렉사, 나강

✍️ 준비

아래 양식을 복사해 스터디 준비를 완료해주세요!

## 💬 생각

<!--강의를 듣고 생각한 내용을 3줄 내로 간단히 정리해주세요!-->

- ...

## ❓ 질문

<!--공부하면서 궁금한 점을 작성해주세요!-->

- ...

## 📚 참고 자료

<!--공부하면서 같이 공부한 자료를 첨부 및 공유해주세요!-->

- [...](...)

[jonyejin]

✔️ 내용 정리

• Table Index를 표현하기 위해서 Hash Table이 아니라 B+Tree를 쓰는 이유?

B+Tree

• 항상 sort 되어있다
• BST의 일반화 (2개 이상의 child node 가능) -> 범위를 여러개 표현할 수 있다고 생각함.
• 진짜 잘만든 자료구조 같아요. 근데 루트 포인터가 계속 바뀌나요?
• select하는 방식 배우기
• 중복키 삽입하는 방법 배우기: leaf node를 하나 더 만드는 방법으로 한다고 함.
• clustered index: PK 쓰는거구나

💬 생각

• 항상 tree라는 자료구조를 컴퓨터에서 많이 쓰는 이유를, 메모리 활용하기 좋은 자료구조라서라고 생각했는데 이게 맞는지 궁금합니다

❓ 질문

• pointer swizzling..? DB주소(물리적) -> 메모리 주소(가상 메모리주소)???

Nodes use page ids to reference other nodes in the index. The DBMS must get the memory location from the page table during traversal.
If a page is pinned in the buffer pool, then we can store raw pointers instead of page ids. This avoids address lookups from the page table.

📚 참고 자료

• (1부) B tree의 개념과 특징, 데이터 삽입이 어떻게 동작하는지를 설명합니다! (DB 인덱스과 관련있는 자료 구조) | 쉬운코드

[CoodingPenguin]

💬 생각

• 이번 강의 내용은 B+ Tree에 관한 내용이 전부였던 것 같다.
• 전에 한 번 공부한 적이 있어서 내용을 이해하는데 어렵지는 않았지만, 생각보다 설명하는 깊이가 얕았던 것 같다.

❓ 질문

• Leaf Node Value를 저장하는 방식이 2가지 있었는데 그 중 "Tuple Data" 방식이 잘 이해가 안 간다.

📚 참고 자료

• [Database] Clustered Index와 Non-Clustered Index | 팡트루야
• [자료구조] 그림으로 알아보는 B+Tree | emplam27.log

[Nagunt]

💬 생각

• B+Tree에 대한 강의
• B의 뜻은 모르지만 아마도 Balanced? (교수 피셜)
  • 항상 정렬되어 있는 데이터 구조. 모든 Action의 시간복잡도가 O(log N)이다. 즉 빠르고 효율적이다.
  • 실질적인 데이터는 맨 끝단 (leaf node)에만 저장되며, 중간 노드는 오직 탐색을 위한 데이터가 저장. 이제까지 알고 있던 tree 구조와는 다른 점이 신기했다.
  • 삽입 시 빈 공간이 없다면 : append or overflow
    • append : 기존 공간을 확장, 분할해서 삽입. leaf node 뿐만 아니라 중간 노드도 수정해 줘야 함.
    • overflow : 기존 공간을 확장하는 것은 동일하지만 오직 leaf node만 확장해서 사용한다. 다른 leaf node와 크기가 달라지는 문제 (복잡해짐)
  • Cluster, Index Scan

📚 참고 자료

• DataBase Index에서 기본적으로 HashTable이 아닌 B-Tree를 쓰는 이유 | 🐺
• [자료구조] 그림으로 알아보는 B+Tree | emplam27.log
• 인덱스의 개념(클러스터, 논클러스터, B-tree)과 인덱스 성능 테스트 | 코딩공장공장장