B+Tree
B-Tree 는 특정 데이터 겁색은 효율적(O(logN))이지만,
모든 데이터를 순회하는 경우, 모든 노드를 방문해야해서 비효율적이다.이런 B+Tree의 단점을 개선한 것이 B+Tree 이다.
B+Tree는 리프 노드에만 데이터를 저장하고
리프노드가 아닌 노드에서는 자식 포인터만 저장한다.리프노드 끼리는 Linked List로 연결되어 있다.
또한 데이터가 반드시 리프노드에만 저장되어 있기 때문에
중간 노드에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.
장점
리프노드의 데이터만 저장하기 때문에 공간 확보를 더 할 수 있다.
따라서 하나의 node에 더 많은 포인터를 가질 수 있어서
트리의 높이가 낮아지므로 검색 속도를 높일 수 있다. ????
Full Scan 하는 경우 리프노트들은 연결리스트로 되어있기 때문에 선형 시간이 소요된다.
B tree의 경우 모든 노드를 확인해야한다.
단점
B tree 의 경우 최적의 경우 root 노드에서 찾을 수 있지만
B+ tree 의 경우 반드시 리프노드까지 가야한다.
인덱스 구현 시 B-Tree 보다 B+tree를 사용하는 이유
인덱스 컬럼은 범위 연산이 자주 발생할 수 있기 때문에
B+tree 내부의 Linked list를 이용하면 효율적으로 할 수 있다.
검색
B-tree의 검색과 동일하다.
참조: B-tree 검색
삽입
key의 수가 최대보다 적은 리프 노드에 삽입하는 경우
해당 노드의 가장 앞이 아닌 경우 단순 삽입
가장 앞인 경우 ????
해당 node를 가리키는 부모 node의 포인터의 오른쪽에 위치한 key를 K로 바꿔준다.
leaf node끼리 Linked list로 이어줘야 하므로 삽입된 key에 Linked list로 연결한다.
key의 수가 최대인 리프 노드에 삽입하는 경우
분할이 필요하다.
만약 중간노드에서 분할이 일어나는 경우 B tree와 동일하다.
리프노드에서 분할이 필요할 경우 중간 key를 부모 노드로 올려준다.
삭제
삭제할 key가 리프노드의 가장 앞에 있지 않은 경우
B-tree의 삭제와 동일하다.
참조: B-tree 삭제
삭제할 key가 리프 노드에 가장 앞에 위치한 경우
이 경우는 리프 노드가 아닌 노드에 key가 중복해서 존재한다.
따라서 key를 노드보다 오른쪽에 있으면서 가장 작은 값으로 바꿔주어야 한다.
