• record 삽입/삭제 시 index entry 정렬이 leaf node(best) 혹은 leaf에서 root 사이 path 상 node들(worst)에서만 국지적으로 발생한다.
  • leaf node가 대부분 entry가 다 채워지지 않기 때문에, leaf node에서의 entry 수정으로 삽입/삭제 처리가 끝난다.
• data file이 search key 기준으로 정렬되지 않아도 사용할 수 있다.
• leaf entries가 dense하기 때문에 record의 주소를 한 번에 찾을 수 있다.

clustering & dense index

• data file이 search key 기준으로 정렬될 필요가 없다. record를 삽입/삭제할 때, data file을 정렬하는 연산을 하지 않는다.
• record가 삽입/삭제 될 때 index entry 정렬을 유지하기 위해 index file 전체가 수정된다.

clustering & sparse index

• data file을 순차 탐색하지 않아도 된다. (nonunique key인 경우)

non-clustering (dense) index

• record가 삽입/삭제 될 때, index entry 정렬을 유지하기 위해 index file 전체가 수정되어야 한다. leaf node에서만 entry를 추가/제거하면 충분하고, worst case에서도 root-leaf node까지 path 상의 node만 수정된다.

multilevel index

• leaf node가 대략 절반 정도 entry가 채워져있으므로 block 내 index entries가 가득 찬 multilevel index와 달리, record 삽입/삭제 시 부모에 영향이 전파되는 경우가 적다.

index-sequential file

• free space 부족으로 인한 overflow block 발생을 해소하는 주기적인 재구성이 필요하지 않다.

[참고] binary tree

• subtree 개수가 많아서 접근 block 수가 적다.