행위

"인덱스 구조"의 두 판 사이의 차이

DB CAFE

(새 문서: = 인덱스 구조 = == B+Tree 란 == # 기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든...)
 
(→‎인덱스 구조)
1번째 줄: 1번째 줄:
 
= 인덱스 구조 =
 
= 인덱스 구조 =
−
== B+Tree 란 ==
+
== B+Tree 인덱스 장점 ==
−
# 기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다.
+
# 인덱스를 이용해 데이터에 엑세스할 때 모든 인덱스 엔트리에 대해 균형(Balance)을 맞춤
−
# 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다.  
+
# 인덱스를 이용한 범위(Range) 스캔 시 Double Linked List를 사용하기 때문에 다른 인덱스보다 더 유리하며 ACESENDING과 DESCENDING도 가능함
−
# B+Tree는 [leaf node] 에만 데이터를 저장하고 leaf node가 아닌 node 에서는 자식 포인터만 저장한다.
+
# OLTP 환경에서 적은 데이터에 엑세스하는 데 유리함
−
# [leaf node] 끼리는 Linked list로 연결되어 있음
+
== B+Tree 인덱스 단점 ==
−
# B+Tree에서는 반드시 leaf node에만 데이터가 저장되기 때문에 중간 node에서 key를 올바르게 찾아가기 위해서 key가 중복될 수 있다.
+
# 분포도(Cardinality)가 낮은 컬럼의 경우 B*TREE 인덱스가 불리함
 +
# OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함
 +
# 인덱스 연산 불가
 +
# 인덱스 확장 시 부하 발생
 +
 
 +
== 인덱스 오퍼레이션 ==
 +
=== 추가 Insert Operation ===
 +
# 테이블에 데이터가 추가되면 해당 테이블에 존재하는 인덱스에도 추가된 데이터의 인덱스 엔트리가 추가된다.
 +
# 테이블에 추가되는 데이터의 인덱스 키(Key) 값의 저장 위치를 찾기 위해 인덱스 리프 블록을 확인해 찾는다.
 +
#: 그리고 인덱스 블록의 여유 공간에 해당 인덱스 엔트리를 추가한다.
 +
# 해당 인덱스 블록에 여유 공간이 없을 경우, 해당 블록은 2개의 인덱스 리프 블록으로 분기돼 인덱스 키들은 다시 정렬되고 분기된 2개의 인덱스 리프 블록을 통해 추가된다.
 +
#: 이 때 리프 블록을 연결하고 있는 브랜치 블록과 루트 블록의 정보가 갱신될 수 있다.
 +
 
 +
=== 삭제 Delete Operation ===
 +
# Insert Operation과 정반대의 작업을 수행한다.
 +
# 데이터가 삭제되면 해당 인덱스 엔트리의 연결이 끊어진다.
 +
#: 그렇게 함으로써 루트 블록으로부터 해당 인덱스 엔트리를 인식하지 못하게 한다.
 +
# 삭제된 인덱스 엔트리의 공간은 추가를 위해 공간 해제를 수행하게 되며, 리프 블록에 하나의 인덱스 엔트리라도 남게 되면 인덱스 리프 블록은 유지되게 된다.
 +
# 많은 인덱스 엔트리가 삭제되면 삭제된 공간은 반납된다.
 +
# 그러나 해당 리프 블록의 전체 데이터가 삭제되지 않는 한 해당 리프 블록은 반납되지 않는다.
 +
# 해당 리프 블록에 새로운 인덱스 엔트리가 추가로 저장되지 않는다면 공간이 낭비되게 된다.
 +
=== 갱신 Update Operation ===
 +
# 삭제와 추가 작업이 동시에 수행되는 작업이다.  
 +
# 테이블에 데이터가 순차적으로 증가해 추가되는 경우 인덱스의 우측으로 인덱스 엔트리가 집중돼 B*TREE의 가장 중요한 특징인 균형(Balance)이 무너지게 된다.
 +
# 또한 죄측 리프 블록으로 인덱스 엔트리가 추가되지 않기 때문에 좌측 리프 블록은 "블록 사용률" 이 낮아지게 된다.
 +
# 삭제가 많거나 또는 인덱스 키가 순차적으로 증가하며 추가되는 테이블은 주기적인 인덱스 재구성(Rebuild)을 통해 인덱스 균형(Balance)을 유지시켜줘야 한다.

2023년 4월 26일 (수) 23:13 판

thumb_up 추천메뉴 바로가기

1 인덱스 구조[편집]

1.1 B+Tree 인덱스 장점[편집]

  1. 인덱스를 이용해 데이터에 엑세스할 때 모든 인덱스 엔트리에 대해 균형(Balance)을 맞춤
  2. 인덱스를 이용한 범위(Range) 스캔 시 Double Linked List를 사용하기 때문에 다른 인덱스보다 더 유리하며 ACESENDING과 DESCENDING도 가능함
  3. OLTP 환경에서 적은 데이터에 엑세스하는 데 유리함

1.2 B+Tree 인덱스 단점[편집]

  1. 분포도(Cardinality)가 낮은 컬럼의 경우 B*TREE 인덱스가 불리함
  2. OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함
  3. 인덱스 연산 불가
  4. 인덱스 확장 시 부하 발생

1.3 인덱스 오퍼레이션[편집]

1.3.1 추가 Insert Operation[편집]

  1. 테이블에 데이터가 추가되면 해당 테이블에 존재하는 인덱스에도 추가된 데이터의 인덱스 엔트리가 추가된다.
  2. 테이블에 추가되는 데이터의 인덱스 키(Key) 값의 저장 위치를 찾기 위해 인덱스 리프 블록을 확인해 찾는다.
    그리고 인덱스 블록의 여유 공간에 해당 인덱스 엔트리를 추가한다.
  3. 해당 인덱스 블록에 여유 공간이 없을 경우, 해당 블록은 2개의 인덱스 리프 블록으로 분기돼 인덱스 키들은 다시 정렬되고 분기된 2개의 인덱스 리프 블록을 통해 추가된다.
    이 때 리프 블록을 연결하고 있는 브랜치 블록과 루트 블록의 정보가 갱신될 수 있다.

1.3.2 삭제 Delete Operation[편집]

  1. Insert Operation과 정반대의 작업을 수행한다.
  2. 데이터가 삭제되면 해당 인덱스 엔트리의 연결이 끊어진다.
    그렇게 함으로써 루트 블록으로부터 해당 인덱스 엔트리를 인식하지 못하게 한다.
  3. 삭제된 인덱스 엔트리의 공간은 추가를 위해 공간 해제를 수행하게 되며, 리프 블록에 하나의 인덱스 엔트리라도 남게 되면 인덱스 리프 블록은 유지되게 된다.
  4. 많은 인덱스 엔트리가 삭제되면 삭제된 공간은 반납된다.
  5. 그러나 해당 리프 블록의 전체 데이터가 삭제되지 않는 한 해당 리프 블록은 반납되지 않는다.
  6. 해당 리프 블록에 새로운 인덱스 엔트리가 추가로 저장되지 않는다면 공간이 낭비되게 된다.

1.3.3 갱신 Update Operation[편집]

  1. 삭제와 추가 작업이 동시에 수행되는 작업이다.
  2. 테이블에 데이터가 순차적으로 증가해 추가되는 경우 인덱스의 우측으로 인덱스 엔트리가 집중돼 B*TREE의 가장 중요한 특징인 균형(Balance)이 무너지게 된다.
  3. 또한 죄측 리프 블록으로 인덱스 엔트리가 추가되지 않기 때문에 좌측 리프 블록은 "블록 사용률" 이 낮아지게 된다.
  4. 삭제가 많거나 또는 인덱스 키가 순차적으로 증가하며 추가되는 테이블은 주기적인 인덱스 재구성(Rebuild)을 통해 인덱스 균형(Balance)을 유지시켜줘야 한다.
원본 주소 "http://dbcafe.co.kr/wiki/index.php?title=인덱스_구조&oldid=8298"