[데이터베이스] Indexing - (2)

*다른 필기*

0607

-p6
recovery - dbms 100만 라인중 20만 라인 할당 되있음
Query Optimization - 어떻게 sql문을 빠르게 실행시킬 것이가
           intelligent가 포함 되 있다
ex) select sno, sname, dept from student where sname = 'Kim'

인텍스 따로 안한 경우
student테이블을 table scan하고 select해서 필터후 project
table에 index를 해놓았다 - 100만개 3초 걸림
sname을 찾는데 sname이 index가 되있으면 sname으로 scan

인덱스가 되있는 경우
index search -> 바로 project

-p7
튜플들을 디스크에 파일 형태로 저장할 때 3가지로 저장함
heap - 아무 생각없이 들어오는대로 저장함(insert순서대로 저장)
       
sorted - 어떠한 순서를 가지고 저장함
    기본적으로 dbms는 기본키의 순서대로 저장한다 
    binary search 가능하다
    소팅을 어떤 속성으로 하느냐가 중요하다//table 하나는 한 속성에 대해서만 sorting되있다
     
indexed - 하나의 table에 속성이 많다
     ex)속성이 20개가 있는데 그걸 다 볼수가 있는데 그것들을 indexing해 놓지 않으면 느려진다
     table이 있으면 속성에 대한 index가 필요하다
     create index idx_student_sname on student(sname);//인덱스가 많을 수록 데이터베이스 업데이트 비용이 많이 든다
          search가 많은 경우는 index를 만드는게 좋다//insert가 많으면 고려

-p8
검색을 도와주는 추가적인 자료구조
data file- 원래 record가 저장된 파일
index는 sequencial searching 하지않고 찾기 위해 만들어 짐

***************************기말고사***************
index가 무엇인지 한 문장으로 표현하는 거 시험에 나온다. 
************************************************** 

index를 어떻게 해야 table보다 빠를 까
기본키로 할 때는 logN번 만에 찾는다
index구조를 가장 쉽게 만드는 방법 필드를 sorting
index uodate비용이 너무 크기 때문에 tree와 hash형태로 가져감
 

---

**내필기**

 

page 8)

indexing 은 트리형태와 hashing형태로 많이 한다. 

tree의 좋은 점은 binary search처럼 logn알고리즘으로 검색이 되고 , insert, delete도 logN만큼 된다. 

 

page9)

DBMS가 disk를 얼마나 적게 읽느냐, 많이 읽느냐에 따라 sql문 성능이 차이가 난다. 

정교한 비용보다는 디스크 비용을 계산을 해보았다.

디스크의 단위는 페이지다. 여기서 몇가지 용어를 정리해보자. 

B : 데이터 페이지의 개수 

R: 각 페이지에 저장된 레코드의 개수 

D: 테이블의 페이지의 개수이다.(디스크를 한번 접근하는 비용이다.) 

만약 student테이블에 

Cardinality = B*R이다. 

 

Table

P1	P2
P3	..

cost모델은 어떤 연산을 수행할 때 비용이 얼마나 들지를 모델링해놓은 것이다. 

 

page10)

레코드는 single insert와 single delete가 가능하다.

heap files : heap file은 맨뒤에 붙이면 된다. 

그냥 넘어가자.

---

page11) 이페이지에서 시험문제 나온다. ** 

 

* scan all recs  (모든 레코드를 스캔한다.)  ex) select * from students

 

1) heap file : 무순서로 레코드가 저장되어있다. >> BD

모든 페이지 : B , 읽는 비용 : D 

 

2) sorted file : sorting이 되어있는 테이블 >> BD

 

3) hashed file: hashing 이 되어있는 테이블  >> 1.25BD

- 전체에 80퍼센트가 차있고, 20퍼센트를 읽어야한다고 치자. 

 

* equality search (학생이름이 홍길동일때로 정확히 딱 검색할때) 

1) heap file : 처음부터 읽는 방법 

- 평균적으로 전체 테이블의 반을 검색해야 학생의 이름을 검색할 수 있기 떄문에 0.5BD

 

2) sorted file : sort가 되어있기때문에, binary search 비용이다.

- log2B에 각페이지 읽어들이는 비용이 D이니까 D log2B

 

3)hashed file :  페이지 한 번읽어도 된다. 

- D이다. 빨간색은 제일 좋다라는 뜻이다. 

 

* range search  : 김씨성인 사람들을 찾자, 2학년인 학생들을 찾자. 

1) heap file  : 처음부터 읽으면 된다. 

- range가 끝날때까지 읽어야하기 때문에 BD이다. 

 

2) sorted file 

- 일단 값의 첫값을 찾아서 학점이 50~60이라고 하면 50인 놈을 먼저 찾자. 그 비용은 log2B이다. 

- 60될때까지 쭉 읽는다.

 

3) hashed file

- 처음부터 읽는 수밖에 없다. 최악의 경우 1.25BD이다. 

 

 

* insert  : 레코드 삽입하기

1) heap file  

- 맨뒤에 삽입한다.

- 맨뒤에 있는 페이지를 읽고, 레코드를 쓰고서 다시 writing해야 하기때문에 2D이다. 

 

2) sorted file 

-일단 search를 해야한다. search를 하고 레코드를 넣어야하는 데 꽉채워져있어서 바로 넣을 수 없다. 

- 그이후에 있는 페이지들을 전부다 읽어서 다시 써줘야한다. 1/2BD이다. 

- 그래서 2*(1/2BD)이다.

 

3) hashed file

- 해쉬가 된 페이지를 읽어서, 다시 writing해야하므로 2D이다. 

 

*delete : 레코드가 어디있는지 찾아야하기때문에 search 비용 증가 

1) heap file  , 2) sorted file 

1/2 read 와 1/2 delete가 발생하므로 search + BD

 

3) hashed file

- 2D 

 

한 테이블은 기본키에 따라 sorted table로 저장되어있다. insert할때 뒤에 다 밀리지 않게 보통 공간을 준다. 

기본키에 대해서 sorted file형태로 테이블이 저장되고,

기본키가 아닌 애트리뷰트는 인덱스로 구성하는데 그 인덱스가 트리형태 또는 해쉬 형태로 만들어진다. 

---

page12,13) 

그래서 우리가 인덱스 얘기를 해볼거다. 

search key field : 검색에 사용되는 애트리뷰트를 말한다. 

학생이름으로 검색할때, search field에 대한 인덱스를 만들어주면 speeding up이 된다.  

 

필요에 따라 multi-attributed로 만들 수 있다. 

인덱스는 B-tree와 B+-tree로 구현이 되어있다. 

B+-tree를 보면 이미 얘기했듯이 트리형태로 되어있고,

binary tree와 다른점은 1) child의 개수가 두개가 아니라 annary이다. 

10개 , 20개 , 30개로 트리가 팽창하고, 2) binary tree와 또 다른점은 밸런싱이 되어있다. --> 모든 레코드의 레벨이 같다. 

 

밸런스를 유지하는 insert와 delete알고리즘이 개발이 되어있다. 

leaf-pages: 더이상 아래로 내려가는 포인터는 없는데 실제로 데이터 엔트리를 가리키는 주소들이 저장되어있다.

(튜플의 주소들을 가리킨다.) 

 

그리고 다른점은 

3) 자기 옆 노드와 양방향으로 링크가 되어있다. 

leaf page를 데이터 엔트리라고하고, non-leaf pages는 인덱스 엔트리라고 한다. 

 

page14)

28을 찾아보자. 

1) 17에서 오른쪽 포인터를 따라간다.

2) 27과 30이 있으니까 중간을 따라간다. 

3) 28이 있느냐 ? 없다.

 

여기서 중요한것은 logmN으로 검색을 할 수 있다. m = 포인터의 개수  

 

15보다 크고 30보다 작은 놈을 찾아라 ; 일단 15를 찾자.

옆으로 가다 33은 30보다 작으므로 16,22,24,27,29를 리턴한다. 

 

insert와 delete인 경우, 28을 넣고 싶은경우 27과 29를 조절하면 된다.

만약 꽉 차있는 경우, split알고리즘을 쓴다. 두개를 쪼개고 중간값을 올려서 조절하는 알고리즘을 쓴다.  

 

---

hash라는 것은 결국 무한정 큰 공간을 작은 공간으로 매핑하는 것이다.

static hashing : primary page가 N개로 고정되어있는 경우이다.

전체학생이 100만명인데 100개로 매핑시키면 충돌이 발생한다는 문제가 있다. 여기서는 자세히 얘기안하겠다.

 

page17)

이제부터 중요한 얘기를 할거다. 

인덱스는 여러분들이 DBA관점에서 쓸 수 있어야한다. DBMS를 사용하는 DBA관점에서 알아야한다.ㅁ

clustered indexing : 중요하다.

clustered indexing은 어떤거냐면 원래 레코드를 저장하는 파일이 있다. 

애트리뷰트에 따른 인덱스가 있다. 데이터가 어떤 필드에 순서대로 저장되어있다.

기본적으로는 순서로 저장되어있다고 하면 primary key순서로 저장되어있다.

학생들이 학번순으로 sorting되어있는데 이름인덱스로 본다면, 이름은 클러스터된 인덱스는 아니다.

 

학생들이 학번순으로 sorting되어있는데, 학번순으로 인덱싱이 되어있으면 clustered이다. 

primary key 인덱싱은 join을 하기 위해 중요하다. 

 

하나의 테이블에는 단하나의 clustered index만 존재한다.