[Database/Theory] 12. index(2) - 내부적 동작

12. index(2) - 내부적 동작

 - 내부적 동작

   * B-Tree(Balanced Tree)라는 구조에 의해 동작한다.

   * 자료구조의 Tree와 같은 구조이며 Root, Leaf와 같은 지칭이 있다.

   * 자료구조에서는 자료를 가진 것을 node라 부르지만 DB의 B-Tree에서는

     Page라 부른다.

   * 한 Page에 8Kbyte의 공간을 차지한다.

   * 특정 Data를 검색할 때, Root page를 시점으로 연결된 Page를 찾아나아간다.

   * table scan보다 확연한 탐색 속도의 차이가 있다.

   * 그러나 Data의 변경작업이(insert, delete, update => CUD라 부르겠다.) 잦으면      역효과가 나타난다.

   * 페이지 분할 작업이 발생되기 때문이다.

   * 가령 특정 페이지에 데이터가 삽입되면 index 특성상 정렬이 먼저 수행되고

     페이지에 공간이 부족하면 새로운 페이지가 생성되어 분할된다.

   * 그렇게 되면 tree의 구조가 크게 변경될 수 있다. 이에 따라 탐색이 기존보다

     복잡해질 수 있다.

   * 그러니까 결론은 분할이 많이 발생되면 시스템의 성능이 떨어진다.

   예시

  이 구조에서 iii와 ggg를 삽입하게 되면 페이지들이 분할된다. 

 - Clustered Index

    * 예시로 users라는 테이블을 생성해서 아래와 같은 데이터들을 삽입하겠다.

    * 데이터를 입력한 순서에 유의한다.

    * 참고로 입력하는 데이터들은 페이지 용량에 맞춰진다. 이러한 페이지들을

      Data Page 혹은 Heap area라 부른다.

create table users(
   id   varchar primary key,
   name varchar
);
 
insert into users values('KYY', '김윤영');
insert into users values('KEH', '김은혜');
insert into users values('HKM', '홍경모');
insert into users values('YHH', '유형환');
insert into users values('YMH', '유민호');
insert into users values('LTG', '이태검');
insert into users values('BSH', '백승현');
insert into users values('KKC', '김경철');
insert into users values('JHJ', '장희정');
insert into users values('JHM', '정희민');
insert into users values('KHS', '김희선');
insert into users values('BCE', '배찬익');

    * Clustered index는 영단어 사전과 유사하다.

    * heap area를 보면 입력한 데이터의 순서가 아닌 index로 지정된 열에 따라

      정렬이 된 후에 위와 같은 구조를 표현하고 있다.

    * 11. index(1) - 개요, 장단점, 종류 에 설명된 바에 의하면 clustered index는

      데이터가 순차적으로 정렬되어 있다는 성질이 있다.

    * Root, Leaf의 구조를 가지고 있으며 Leaf page 자체가 Data임을 알 수 있다.

    * non-clustered index보다 비교적으로 검색속도가 빠르지만 변경작업은 느리다.

 - Non-Clustered Index

    * clustered index와 같은 테이블로 예시를 들어본다.

    * 다시 위로 올리기 귀찮아 할까봐 다시 적어본다.

    * 역시 입력한 데이터의 순서에 유의한다.

create table users(
   id   varchar primary key,
   name varchar
);
 
insert into users values('KYY', '김윤영');
insert into users values('KEH', '김은혜');
insert into users values('HKM', '홍경모');
insert into users values('YHH', '유형환');
insert into users values('YMH', '유민호');
insert into users values('LTG', '이태검');
insert into users values('BSH', '백승현');
insert into users values('KKC', '김경철');
insert into users values('JHJ', '장희정');
insert into users values('JHM', '정희민');
insert into users values('KHS', '김희선');
insert into users values('BCE', '배찬익');

   * clustered index와 달리 입력한 순서대로 Data page가 구성된다.

   * non-clustered index는 Data page를 건드리지 않고 

     별도의 index page를 생성한다.

   * data page를 참조하여 non-clustered index page의 leaf에서 index로 설정한

     열에 따라 데이터들이 정렬된다.

   * leaf에 1000 + #2와 같은 표기는 RID(Row ID, 데이터 위치 포인터)라 부른다.

     페이지 번호와 offset에 따라 실제 data로 이동된다.

   * clustered index와 비교하면, 데이터를 탐색할 때 

     거치는 페이지 수는 non-clusetered index가 1회가량 더 거치게 된다.

   * 물론 간단한 예시이지만, 데이터들이 방대해지면 큰 차이가 일어날 것이다.

   * 고로 Clustered index가 더 탐색속도가 빠르다.

 - 데이터의 추가(Clustered Index,  Non-Clustered Index)

   * 역시 위로 올리기 귀찮으니 한번 더 예시의 테이블을 작성한다.

create table users(
   id   varchar primary key,
   name varchar
);
 
insert into users values('KYY', '김윤영');
insert into users values('KEH', '김은혜');
insert into users values('HKM', '홍경모');
insert into users values('YHH', '유형환');
insert into users values('YMH', '유민호');
insert into users values('LTG', '이태검');
insert into users values('BSH', '백승현');
insert into users values('KKC', '김경철');
insert into users values('JHJ', '장희정');
insert into users values('JHM', '정희민');
insert into users values('KHS', '김희선');
insert into users values('BCE', '배찬익');

   * 여기에서 두 개의 데이터를 추가한다.

insert into users values('SMK', '서민기');
insert into users values('KJH', '김주현');

   * Clustered Index와 Non-Clustered Index의 B-Tree 구조를 본다.

   * 다시 한번 더 정리한다.

   * Clustered Index는 생성될 때 데이터 페이지 전체를 다시 정렬한다.

   * 대용량의 데이터가 있다면 시스템 부하가 발생될 수 있다.

   * Leaf가 곧 데이터다 따라서 인덱스 자체에 데이터가 포함된 것이라 볼 수 있다.

   * Non-Clustered Index와 비교할 때 검색속도는 빠르지만 변경작업은

     페이지 분할에 의하여 느리다.

   * 테이블 한개에 Clustered Index 하나만 생성이 가능하므로,

     어느 열에 Clustered Index를 지정하느냐에 따라 시스템 성능이 좌우된다.

   * Non-Clustered Index는 생성될 때 페이지를 그대로 둔 채,

      Index를 구성한다.

   * Leaf가 RID다.

   * Clustered Index와 비교할 때 검색속도는 느리지만 변경작업은 빠르다.

     (Heap Area뒤에 추가만 하면 되고 Leaf에서는 약간의 변동만 하면 되니까)

   * Non-Clustered Index는 한 테이블에 여러개를 생성할 수 있지만 

     지속적인 남용은 시스템의 성능이 저하되므로 필요한 것만 지정하도록 한다.

 - Clustered Index,  Non-Clustered Index의 혼합

   * 한 가지 추가한 예시로 설명을 본다.

create table users(
   id    varchar primary key,
   name  varchar unique,
   phone varchar
);
 
insert into users values('KYY', '김윤영', '011');
insert into users values('KEH', '김은혜', '016');
insert into users values('HKM', '홍경모', '011');
insert into users values('YHH', '유형환', '017');
insert into users values('YMH', '유민호', '016');
insert into users values('LTG', '이태검', '017');
insert into users values('BSH', '백승현', '011');
insert into users values('KKC', '김경철', '018');
insert into users values('JHJ', '장희정', '016');
insert into users values('JHM', '정희민', '011');
insert into users values('KHS', '김희선', '018');
insert into users values('BCE', '배찬익', '016');

   * 구조는 아래와 같은 그림으로 형성되고 빨간색 글자를 보면

     데이터를 탐색하는 과정을 볼 수 있다.

   * Non-Clustered Index를 탐색하고 Clustered의 Root Page로 찾아가

     찾고자 하는 데이터를 탐색하는 순서로 되어있다.

   * 기존에 있는 Non-Clustered Index의 Leaf는 RID로 되어 있었지만

     혼합이 되면서 Clustered Index의 Key Value로 되어있다.

   * 이유 : 혼합하지 않고 분리되어 RID를 그대로 사용된다면 검색하는데 있어

     더 빠르겠지만, 

     새로운 데이터가 추가되면 Clustered Index의 Data page가 재구성되고

     RID의 표기가 모두 변경된다. 

     그 결과로 Non-Clustered Index 전체가 재구성되면서 

     엄청난 시스템 부하가 발생될 소지가 있다.

   * 그러니까 결론은 Non-Clustered Index, Clustered Index가 혼합되면 

     RID표기는 삼가한다.

   * 검색의 손해는 있지만 CUD의 손해보다는 확연히 작기 때문에 감안할 수 있다.

 - 용어

   * table scan : 테이블의 모든 데이터를 처음부터 끝까지 탐색하는 것.

   * index seek : Non-Clustered Index에서 데이터를 찾는다는 의미.

   * Clustered Index Seek : Clustered Index에서 데이터를 찾는다는 의미.

   * Clustered Index Scan : table scan과 동일한 의미. 

                                   Clustered Index의 Leaf가 Data Page이기 때문이다.

   ( Seek과 Scan은 다른 의미다.

     인덱스 검색을 위해 where절에 해당 인덱스의 이름을 작성하도록 한다.)