B+Tree

  • B-Tree 의 경우 단일 검색은 빠르지만 Full scan 을 하기 위해서는 결국 트리의 모든 노드를 방문해야 하기 때문에 비효율적이랜다
  • 어쨋든 그래서 B+Tree 의 특징은 다음과 같다
    1. 데이터는 리프노드에만 저장된다
    2. 리프노드가 아닌 노드는 자식의 포인터와 자식을 찾아가기 위한 Key 만 들어간다
    3. 데이터 노드인 리프노드는 링크드 리스트맹키로 일렬로 연결되어 있다.