[CS186] Introduction to Database Systems - Week 3

⛅ B+ Trees ⛅

인덱스

2. Properties

• 정렬되어 있고 자식 속성을 가지고 있기 때문에 트리 아래로 leaf를 순회하면서 원하는 특정 record를 찾을 수 있다 (BSTs, binary search trees와 비슷함)

5. Sorting Records

Alternative 1: By Value

• leaf pages = data pages
• 레코드에 대한 포인터를가 아닌 실제로 레코드를 가지고 있다
• 구현하기 쉽지만 같은 파일에 multiple indexes를 만들 수 없다는 단점이 있다

Alternative 2: By Reference

• leaf pages는 해당하는 레코드의 포인터를 가지고 있다
• multiple indexes가 가능하다

Alternative 3: By List of References

• leaf pages는 포인터 리스트를 가지고 있다

 

6. Clustering

데이터 페이지의 데이터가 어떻게 정리되어 있는지

 

unclustered

• 정돈되어 있지 않다

clustered

• 데이터 페이지가 B+ tree의 인덱스와 같이 정렬되어 있다. 인접한 키를 가지고 있는 2개의 레코드는 같은 페이지에 위치할 확률이 크기 때문에 2번째 레코드를 읽을 때는 캐시된 페이지에서 가져오면 된다
• unclustered 인덱스와 비교해서 clustered 인덱스는 범위 탐색에 유리하지만 유지하는 비용이 더 크다

 

7. Counting IO's

• 1. read the appropriate root-to-leaf-path
• 2. read the appropriate data page(s)
• 3. write data page
• 4. update index page(s)