인덱스(Index)와 해싱(Hashing)

• 인덱스(Index)의 개요
  • 인덱스의 정의
    • 인덱스는 데이터 레코드(튜플)들을 빠르게 접근하기 위해 <키 값,포인터>쌍으로 구성되는 데이터 구조인데, 포인터는 해당 키를 가지는 1개 이상의 레코드를 가리킴
    • 기본키를 위한 인덱스를 기본 인덱스라 하고, 기본 인덱스가 아닌 인덱스를 보조 인덱스라고 함
    • 대부분의 관계형 DBMS에서는 모든 기본키에 대해서 자동적으로 기본 인덱스를 생성함
  • 밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index)
    • 밀집 인덱스
      • 인덱스 레코드는 모든 키 값에 대해 나타남
        (즉, 데이터 파일의 각 레코드의 키 값이 인덱스 엔트리에 포함)
      • 인덱스 레코드는 키 값과 해당 키를 가지는 첫 번째 레코드에 대한 포인터를 포함
    • 희소 인덱스
      • 인덱스 레코드는 키 값에 대해 단지 몇 개만 나타남
        (즉, 일부 키 값에 대해서만 인덱스에 엔트리를 유지)
      • 일반적으로 각 블록마다 한 개의 탐색 키 값이 인덱스 엔트리에 포함됨
      • 레코드가 검색키에 의해 연속적인 순서로 되어 있을 때 적절함
      • 밀집 인덱스보다 더 적은 공간을 차지하고, 삽입과 삭제에 대한 유지 부담이 더 적음
      • 일반적으로 레코드를 찾는 데 밀집 인덱스보다 느림
           
• 이진 탐색 트리(Binary Search Tree)
  • 트리의 조건
    • 루트(Root) 노드라 불리는 특정한 1개의 노드가 존재
    • 루트 노드와 리프(Leaf) 노드를 제외한 나머지 노드들은 자식 노드를 가짐
    • 순환(Cycle)을 허용하지 않음
  • 트리 관련 용어
    

이름	내용	예
루트노드	트리의 최상위 노드	A
차수(Degree)	각 노드가 가지고 있는 가지의 수를 의미 트리의 데이터 구조 정의 시 몇 개의 노드 포인터가 필요한지를 결정	A의 차수는 3 G의 차수는 2
트리 차수	트리를 구성하는 노드의 차수 중 최대값	3 이진 트리의 차수는 2
리프 또는 단말노드 (Leaf or Terminal Node)	차수가 0 인노드	E,F,K,L,H,I,J
레벨(level)	루트 노드의 레벨을 0으로 하여 순서적으로 증가하는 값
깊이(Depth)	가장 높은 레벨	3
부모 노드(Parent Node)	특정 노드의 바로 위(상단)에 위치하며, 가지로 이어진 노드	B와 D의 부모 노드는 A
자식 노드(Child Node)	특정 노드의 바로 밑(하단)에 위치하며, 가지로 이어진 노드	C의 자식 노드는 F,G
형제 노드(Sibling Node0	부모 노드가 같은 자식 노드들	C의 형제 노드는 B,D

• 이진 탐색 트리의 개념 및 특징
  • 트리를 구성하는 모든 노드의 차수가 2를 넘지 않는 트리, 즉 하나의 노드는 2개의 자식노드(또는 서브트리)를 가질 수 있음
  • 트리 T의 좌측 모든 노드들의 값은 T의 루트 노드 값보다 작고, 우측 모든 노드들의 값은 루트 노드보다 크며, 트리 T의 좌우측 트리도 이진 탐색트리
  • 이진 탐색 트리에서 노드내의 값은 오름차순으로 유지하며, 레벨 k의 최대 리프 노드 개수는 2^k
  • 이진 탐색 트리를 일반화한 m-원 탐색 트리에서는 한 노드가 최대 m-1개의 키와 m개의 자식 노드를 가짐
• 이진 탐색 트리의 종류
  • 포화 이진 트리(Full Binary Tree)
    깊이가 K 일때 전체 노드 수가 2^k-1 이고, 레벨마다 노드로 꽉 찬 트리, 즉 리프 노드를 제외한 모든 노드들이 왼족 자신 노드와 오른쪽 자식 노드를 모두 가지는 트리
  • 완전 이진 트리(Complete Binary Tree)
    깊이가 k일 때 레벨 k-1까지는 포화 이진 트리이고, 레벨 k에서 노드가 왼쪽부터 채워지는 트리, 즉 포화 이진 트리의 노드를 좌에서 우로, 위에서 아래로 번호를 붙였을 때 번호가 큰 뒤쪽 노드만 생략된 트리
  • 사향 트리(Skewed Tree)
    노드가 죄측 또는 우측으로 치우친 트리, 즉 리프 노드를 제외한 모든 노드들이 한 방향의 자식 노드만 가진 트리
• 이진 탐색 트리 순회 방식
  • 전위(Preorder) 순회 방식 : 처리 순서가 루트, 왼쪽, 오른쪽 순
  • 중위(Inorder) 순회 방식 : 처리 순서가 왼쪽, 루트, 오른쪽 순
  • 후위(Postorder) 순회 방식 : 처리 순서가 왼쪽, 오른쪽, 루트 순
       

• B-Tree        
  • B-Tree의 개념
    • 루트에서 리프 노드까지 모든 경로의 길이가 같은 균형(Balanced) m-원 탐색트리
    • 루트와 리프를 제외한 모든 노드는 차수의 1/2이상의 자식 노드를 가짐
    • 모든 노드(루트, 리프, 비리프 노드)가 해당 레코드 주소를 가지고 있으므로 리프 노드에 도달하기 전에 원하는 레코드 주소를 얻을 수 있음
    • 키의 삽입과 삭제시 노드의 분열과 합병이 발생할 수 있음
    • B-트리에서의 순차 검색은 중위 순회 방식(Inorder Traversal)으로 가능
    • 노드 오버플로우 발생시 노드를 즉시 분할하므로, 잦은 노드 분할이 발생할 수 있음
    • 차수 m인 B-Tree의 특징
      • 모든 노드는 최대 m개의 서브트리를 가짐
      • 루트 노드와 리프 노드를 제외한 모든 노드는 최소 [m/2]개, 최대 m개의 서버트리를 가짐
      • 루트 노드는 리프 노드가 아닌 이상 적어도 두 개의 서브트리를 가짐
      • 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 작음
      • 모든 리프 노드는 같은 레벨에 있음
      • 한 노드안에 있는 키 값들은 오름차순을 유지
  • B⁺-Tree의 개념
    • B-Tree의 변형된 형태로, 인덱스 세트(Index Set)와 순차 세트(Sequence Set)로 구성
      • 순차 세트
        • 모든 리프 노드들로 구성되며, 모든 키와 레코드 정보를 가짐
        • 키 순서에 의한 레코드 접근을 제공하는 선형적이고 순차적인 방법 지원
      • 인덱스 세트
        • 순차 세트에 직접 접근을 제공하기 위해 사용
        • 해당 키 값을 갖는 리프 노드(즉, 순차 세트)에 신속하게 직접 접근하기 위한 경로를 제공
    • 모든 키 값은 리프 노드에 존재하고, 트리의 레벨이 균형을 유지하므로 균등한 응답 속도를 보장
    • 리프 노드만이 해당 레코드 주소를 가지고 있으므로 리프 노드에 도달해야 원하는 레코드 주소를 얻을 수 있음
    • 순차 접근이 용이하나 키 값이 인덱스 세트와 순차 세트에 중복해서 존재
    • 노드 오버플로우 발생 시 노드를 즉시 분할하므로 잦은 노드 분할이 발생할 수 있음
    • 차수 m인 B⁺-Tree의 특징
      • 루트 노드와 리프 노드를 제외한 모든 노드는 최소 [m/2]개 , 최대 m개의 서브트리를 가짐
      • 루트 노드는 0 또는 2에서 m개 사이의 서브트리를 가짐
      • 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 적음
      • 모든 리프 노드는 같은 레벨에 있음
      • 한 노드 내에 있는 키 값들은 오름차순을 유지하고, 순차 세트 내의 리프 노드들은 모두 링크로 연결되어 있음
  • B*-Tree의 개념
    • B-Tree의 변형된 형태로써 삽입 시 빈번한 분할 현상을 줄인 트리
    • 루트와 리프를 제외한 노드는 2/3 이상 채워져야 함
    • 노드가 오버플로우되면, 여유 공간이 있는 형제 노드에 재분배 과정을 거친 후 키를 삽입
    • 노드 분할은 모든 형제 노드가 다 차있을 때 수행되므로 노드 분할이 지연
    • 순차 접근이 어려우나 삽입 시 분할 현상이 최소화
    • 차수 m인 B^*-Tree의 특징
      • 루트 노드와 리프 노드를 제외한 모든 노드는 최소 [(2m-2)/3]개 , 최대 m개의 서브트리를 가짐
      • 루트 노드는 그 자체가 리프가 아닌 경우 적어도 2개의 서브트리를 가짐
      • 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 적음
      • 모든 리프 노드는 같은 레벨에 있음
      • 한 노드 내에 있는 키 값들은 오름차순을 유지
           
• 비트맵(Bitmap) 인덱스
  • 개념
    • 하나의 릴레이션에서 검색 시 빠른 성능을 제공하기 위해 분포도가 낮은(즉, 같은 속성값을 갖는 튜플 수 가 많은) 속성에 대해서 비트맵을 구성
    • 다중 키를 가진 질의를 쉽게 하기 위해 고안된 특수화된 형태의 인덱스로서, AND/OR 처리에 매우 유용함
  • 구성
    • 인덱스 대상의 속성값을 비트(Bit) 값인 0 또는 1 로 변환하여 인덱스 키로 사용하는 방법
    • 각 레코드의 해당 속성 값에 대해 대응되는 비트맵 비트(0,1의 값)를 설정하기 때문에 릴레이션에 있는 레코드의 수만큼 비트를 가짐
    • 비트맵 인덱스의 구성 예
         
  • 특성
    • 대용량 데이터베이스 환경에서 조회 목적의 응용 프로그램에 적합하지만, 새로운 속성값이 삽입되거나 삭제될 때 비트맵 인덱스를 재생성 해야 하기 때문에 유지보수 비용이 많이 요구됨
    • OLTP(OnLine Transaction Processing)에 적용하기 어려움
  • B-Tree와 비트맵 인덱스의 비교

항목	B-Tree	비트맵 인덱스
인덱스 검색 속도	필요로 하는 인덱스 값만 검색이 가능 상대적으로 소량의 데이터를 검색할 때 유리	항상 전체 인덱스를 검색해야 함 상태적으로 대량의 데이터를 읽을 때 유리
인덱스 크기	인덱스 크기가 비트맵 인덱스 보다 매우 큼 비트맵 인덱스보다 크기에서 백배 이상 차이 날 수 있음	인덱스 크기가 매우 작음(즉, 저장 공간이 적음)
인덱스의 변경관리	트리 알고리즘에 의해 손쉽게 인덱스에 대한 키의 입력, 갱신, 삭제가 가능	키의 삽입, 갱신, 삭제 시 전체 인덱스를 조정해야 하는 부담 존재 인덱스를 재생성하는 비용과 유사
연산 능력	AND 연산에는 좋은 성능을 나타내나 OR 연산이나 != 연산의 성능은 매우 나쁨	AND, OR 연산은 비트 연산을 통해 빠르게 처리 가능
분포도	데이터 분포도가 높은(좋은) (즉, 같은 속성값을 갖는 튜플 수가 적은)속성에 적합	데이터 분포도가 낮은 속성에 적합

   

• 트라이(Trie)
  • 개념
    트라이는 탐색을 위한 키 값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키 값을 구성하는 데이터 구조
  • 구성
    • 트라이의 차수는 키 값을 표현하기 위해 사용하는 문자의 수, 즉 기수(Radix)에 의해 결정됨
      숫자로만 구성된 키인 경우 기수는 10 이고, 알파벳 문자로만 구성된 키인 경우 기수는 26 이므로 각각의 차수는 10과 26이됨
    • 트라이 노드의 크기는 차수에 의해 결정되고, 트라이의 높이는 키 필드의 길이에 의해 결정됨
      • 차수가 10이면 인덱스 노드는 10개의 포인터로 구성되고, 숫자로만 이루어진 키 필드의 길이가 7인 경우 트라이 높이는 7이됨
  • 특성
    • 키 의 삽입 및 삭제 시 노드의 분열과 병합이 발생하지 않음
    • 키 값이 문자열 또는 숫자일 경우 일련의 키 값들에 대해 일부분이 같은 문자나 숫자로 구성되었을 때 적합
    • 가변 길이의 키 값을 효과적으로 나타낼 수 있으며, 키 값의 분포를 미리 예측할 수 있으면 기억 장소를 절약할 수 있음
         
• 해싱(Hashing)
  • 해싱의 개요
    • 해싱 함수를 사용하는 탐색 방법
    • 레코드 키를 가지고 해싱 함수의 계산을 통해 변환되어 나온 주소에 해당 레코드를 저장
    • 레코드 검색 시 주어진 레코드 키로부터 해싱 함수에 의해 주소를 계산해서 해당 레코드에 접근
    • 해싱 방법을 기초로 만들어진 파일을 직접 파일(Direct File)이라고 함
  • 해싱 관련 용어
    • 버킷(Bucket) : 동일한 해시 주소를 갖는 레코드들이 저장될 한 구역을 의미하며, 버킷의 크기는 같은 해시 주소에 저장될 수 있는 레코드의 수를 의미
    • 슬롯(Slot) : 1개의 레코드를 저장할 수 있는 공간으로, n개의 슬롯이 모여 하나의 버킷을 형성
    • 충돌(Collision) : 레코드를 삽입할 때 서로 다른 2개 이상의 레코드가 같은 해시 주소를 갖는 현상
    • 동의어(Synonym) : 같은 해시 주소를 갖는 레코드들의 집합
    • 오버플로우(Overflow) : 계산된 해시 주소의 버킷 내에 저장할 기억 공간이 없는 상태
  • 해싱의 장.단점

장점	단점
검색 방법 중 가장 빠름 오버플로우가 발생되지 않을 경우, 레코드 검색 시 한번의 디스크 접근으로 가능 이진 탐색보다 많은 기억 장소를 차지하지만, 기억 공간이나 속도 측면에서 우수함	오버플로우가 발생될 경우 처리 비용이 커지고, 기억장소가 낭비됨 적당한 해시 함수의 선정이 중요함 기억 공간 할당 크기를 알 수 없으므로, 해시 테이블을 위한 기억 장소 할당이 어려움

• 해싱 함수의 기본 기술
  • 계수 분석(Digit Analysis)
    키 값을 구성하는 숫자의 분포를 파악하여 분포가 비교적 고른 자리부터 필요한 자리만큼 선택하여 레코드주소로 결정하는 방법
  • 제산(Division)
    • 키를 임의의 양의 정수로 나눈 나머지를 그 키의 레코드를 저장하는 주소로 결정하는 방법
    • 키를 K, 양의 정수를 n이라고 할 때 해싱 함수는 h(K) = K mod n (0 ≤ h(K) < n)
  • 제곱(Mid-square)
    키 값을 제곱한 후, 이 값이 중간 부분의 값을 택하여 레코드 주소로 결정하는 방법
  • 예) h(265) = 70225의 중간값 = 022
  • 폴딩(Folding)
    키를 여러 부분으로 나누고, 나눠어진 각 부분의 값을 모두 더하거나 보수를 취해 더하여(XOR; eXclusive OR)레코드 주소를 결정하는 방법
  • 기수 변환(Radix Transformation)
    주어진 키 값을 어떤 특정한 진법의 수로 간주하여, 다른 진법으로 변환하여 레코드 주소를 구하는 방법
• 해싱 충돌 해결 방법
  • 선형 조사(Linear Probing)
    • 해당 주소에서 충돌이 일어난 경우 해당 주소부터 차례대로 조사해서 가장 가까운 빈 공간을 찾아서 레코드를 저장하는 방법
    • 개방 주소법(Open Addressing)이라고도 함
    • 해시 테이블의 구조가 간단하고, 탐색 시 포인터를 사용하지 않음
    • 충돌이 빈번한 경우, 오버플로우 구역에서 탐색할 주소의 수가 증가
  • 버킷 주소법(Bucket Addressing)
    • 레코드의 모임인 버킷에 대하여 연결 리스트(Linked List)를 사용하는 방법
    • 하나의 해시 주소에 가능한 최대 수의 동의어를 저장할 수 있는 공간을 할당
    • 특정 해시 주소에 대한 모든 동의어들은 해당 주소의 버킷에 순차적으로 저장
    • 폐쇄 주소법(Close Addressing)이라고도 함
    • 버킷의 크기에 따라, 버킷이 가득 차는 경우와 비는 경우의 불균형 발생이 가능
  • 이중 해싱(Double Hashing)
    • 오브플로우된 동의어를 오버플로우 구역에 저장할 때 2차 해시 함수를 사용하는 방법
    • 여러 개의 해싱 함수를 적용하는 방법으로, 오버플로우가 발생하지 않을 때까지 여러 개의 해싱 함수를 적용
    • 평균적으로 선형 조사보다 탐색 비용이 적음
    • 충돌이 빈번한 경우 오버플로우 구역에서 탐색할 주소의 수가 증가
  • 독립 오버플로우 구역(Separate Overflow Area)
    • 별도의 독립된 오버플로우 구역을 할당하여 오버플로우된 모든 동의어들을 순차적으로 저장하는 방법
    • 충돌이 빈번한 경우 오버플로우 구역에서 탐색할 주소의 수가 증가하는 문제를 해결
    • 오버플로우된 동의어에 접근하기 위해서는 오버플로우된 구역에 있는 모든 레코드들을 순차적으로 검색해야 함
  • 동의어 체인(Synonym Chaining)
    • 동일한 해시 테이블 내에서 동의어들을 연결 리스트(Linked List)로 구성
    • 오버플로우 발생 시 선형 조사나 오버플로우 구역등을 이용하여 저장하고, 탐색 시 해당 주소에 대한 포인터를 사용하는 방법
    • 충돌 시 순차 검색을 피할 수 있으므로 탐색 시간이 단축됨
       

• 동적 해싱(Dynamic Hashing)
  • 개념
    • 데이터베이스가 확장 또는 축소(즉, 레코드 수가 확장 또는 축소)되는 데에 맞추어 해싱 함수를 동적으로 변경시키는 해싱 기법
    • 키 값을 사용하여 이진 트리를 동적으로 변화 시킴
    • 데이터베이스가 커지면서 버킷들을 쪼개거나 합치는 것이 동적 해싱의 기본 개념
    • 확장 해싱(Extendible Hashing)은 동적 해싱의 한 형태로, 트리의 깊이가 2인 특별한 경우
  • 등장 이유
    • 일반적인 해싱에서는 버킷 크기가 고정되어 있어 다음과 같은 문제가 발생
      • 현재의 데이터베이스 파일 크기에 알맞은 해싱 함수를 선택하면 데이터베이스 확장 시 성능이 낮아짐
      • 이후에 데이터베이스에서 사용하게 될 만한 파일 크기를 산출하여 해싱 함수를 선택하면 초기에 디스크 낭비가 심해짐
    • 이러한 문제를 해결하기 위해 데이터베이스 파일의 크기에 따라 해싱 함수를 동적으로 변경할 필요성이 생김
         
• 클러스터(Cluster)
  • 개념
    • 클러스터 : 디스크로부터 레코드를 읽어오는 시간을 줄이기 위해서 조인이나 자주 사용되는 테이블의 레코드들을 디스크의 같은 위치 또는 인접한 위치에 저장하는 방법
    • 해시 클러스터 : 클러스터의 다른 유형으로 레코드들의 클러스터에 해싱 함수를 사용하여 레코드가 어느 위치에 저장되어 있는지 물리적인 위치를 결정하는 방법
  • 특징
    • 클러스터는 함께 저장되어야 하는 레코드들을 구분하는 데 사용되는 클러스터 키를 가지며, 클러스터 키는 하나 이상의 필드로 구성될 수 있음
    • 클러스터의 테이블은 클러스터 키에 대응되는 필드를 가짐
    • 클러스터 된 테이블의 레코드는 정규 테이블에 저장된 것처럼 조작이 가능
    • 클러스터 키의 필드 중 하나를 갱신하면 물리적으로 레코드를 재배치하는 작업이 발생할 수 있음
    • 클러스터 키는 기본키와는 독립적이며, 보통 성능 향상을 목적으로 함
    • 클러스터 된 레코드에 대한 임의 접근(Random Access)은 빨라지지만, 전체 테이블 스캔(Full Table Scan) 속도는 느려짐
         
  • OLTP - 네트워크 상의 다수의 사용자가 실시간으로 데이터베이스의 데이터를 갱신하거나 조회하는 등의 단위 작업을 처리하는 방식