Multilevel Indexes
: blocking factor(=fanout) 을 늘림으로써, 남는 search space 를 줄이는 것
First level : index file 그 자체
Second level : first level에 대한 Primary index
Third level : second level에 대한 Primary index
ISAM : Indexed Sequential Access Method ➡️ ordering key field 에 따라 multilevel primary index 들이 정렬돼있는 것
왜 Dynamic 을 사용하는가?
➡️ ISAM 은 여전히 insertions 과 deletions 하기 어려움
해결방법 ⬇️
- 각 index blocks 별로 새로운 엔트리 삽입을 위한 공간을 남겨둠
- 적절한 insertion/deletion 알고리즘을 사용함
Search Trees
- fanout 이 p 일때
+ 각 노드는 최대 p-1 개의 search 값을 가짐
+ p 개의 (node) pointer을 가짐
+ ex) fanout 이 3 이라면
+ | P_1 | value | P_2 | value | P_3 |
+ 2개의 search 값과 3개의 노드 포인터를 가짐
B+ -Tree : 가장 널리 사용되는 Index
Insert/Delete :
(p = fanout, N = # leaf pages)
- 모든 leaf node 에 도달하는 시간이 ==height== 로 같음
- 🔆 root node 를 제외하고 모든 노드는 50% 이상 채워져 있어야 함
- 한 노드는 d <= m <= 2d 개의 엔트리를 가질 수 있음 (d=트리의 order)
+ ex) 3차 트리에서는 한 노드에 최대 6개까지 저정할 수 있음 - Equality 와 range-searches 를 효율적으로 지원함
Internal nodes : 바로 검색할 수 있도록. data records가 저장돼있는 것이 아님
Leaf nodes : data pointers 을 저장함
- 서로 연결돼있음
- search field 가 ==key field== 이면, data pointer 은 record를 가리킴
- search field 가 ==nonkey field== 이면, data pointer 은 block을 가리킴
인덱스 엔트리 삽입하기
- leaf L 을 찾음
- L 에 충분한 공간이 있다면 DONE!
- L 에 공간이 없는 경우,
- L 을 쪼개야 함. (L 과 L2 로)
- 고르게 재분배를 한 후, middle key 를 부모 노드에 COPY UP
- COPY UP 하는 이유 : leaf node는 데이터를 실제로 저장하는 노드이므로 본인이 엔트리를 계속 지니고 있어야 함
- L2 를 가리키는 인덱스 엔트리를 L 의 부모 노드에 삽입함
- 반복
- index node를 쪼갤 때는, 엔트리들을 고르게 재분배하고 middle key 를 부모 노드에 PUSH UP ➡️ 현재 노드에는 남겨두지 않는 것
- root 를 쪼개면 height 가 늘어남
1. Redistributing 함으로써 height을 유지할 수도 있음 BUT! ✅ DISK I/O 가 증가해서 실전에선 사용 X
인덱스 엔트리 삭제하기
- root부터 시작해서 해당 엔트리가 속해 있는 leaf L 을 찾음
- 엔트리를 삭제함
1. L 이 최소 half-full 이라면 DONE!
2. L 에 d-1 개 엔트리만 남았다면,
1. 옆 형제 노트에게 엔트리를 빌려서 re-distribute
1. 부모노드에는 삭제된 search key를 대신하여 새로운 key가 COPY UP
2. 불가능하면 L 과 형제노드를 merge ➡️ L 의 부모노드에서 merge된 노드를 가리키는 엔트리를 삭제해야 함!
3. merge가 root 노드까지 일어나면 height 가 줄어듦
B+ - Tree in Practice
-
Typical order : 100
+ Order = 최소 search values
+ 평균 fanout = 133 개 -
보통 height 는 3~4
-
Top level (Root node) 는 항상 buffer pool 에 고정돼있어야 함
-
대부분 sorted file 보다 성능 good
➕ B-tree와 B+ -tree 의 차이점 : B-tree 는 모든 노드에 레코드를 가지지만, B+ -tree는 오직 leaf node에서만 레코드 포인터를 가짐
👩🏻💻