[database] Tree-Structured Indexes (ISAM과 B+ Tree)

본 게시글은

서울대학교 데이터사이언스대학원 이상원 교수님의

데이터사이언스 응용을 위한 빅데이터 및 지식관리시스템 수업을

학습을 목적으로 재구성하였습니다

---

중간에 학회준비 때문에 급하게 올인한다고

수업 내용 정리를 못했다..

그래서 학회가 끝난 뒤에 몰아서 하려했는데

양도 너무 많고 기억도 잘 안나서 쉽지 않은 것 같다 ㅎㅎ..

그래도 어떧ㅎ게든 차근차근 해보려한다

 

이번 내용은 Database에서 index를 처리하는 법이고

가장 대표적인 tree-structured indexes구조이다

 

 

RDBMS의 전체 시스템에서

Files and Access Methods 부분에 해당한다

 

access method에는

전체를 scanning하는

full scanning과 index기반 method가 있다

 

 

 

본 내용을 통해 우리가 알아야하는 것들이다

tree structured index에 대해서 배우고

B+ tree에 대해서 배운다

 

 

인덱싱 문제에 대해서부터 알아보자

인덱싱 문제는 예전부터 해결해야하는 과제였다

 

인덱싱이란 한 마디로 정의하면

큰 데이터를 주고 그 subset을 찾는 문제이다

 

여러 인덱싱 해결기법으로는

bitmap, hash index 등이 있고

공간데이터와 같은 다차원 데이터에 대해서는

R-Tree 방식이 있다

 

또한 위 방법들을 활용해서 검색하는 것을

symbolic search라고도 한다

반대되는 개념으로는 semantic search가 있는데

vector embedding을 통해서 검색하는 것이 대표적인 semantic search이다

한마디로 symbolic search는 정확히 그 데이터를 찾는 것이라면

semantic search는 정확하게 일치하지 않아도

유사하다고 판단되면 해당 데이터를 내뱉는 것이다

 

 

 

인덱싱은 원하는 정보를 키워드를 바탕으로 빠르게 찾는 역할을 한다

 

예를 들어서 위 예시에서

A가 50000인 데이터를 찾으려고 한다

 

대부분의 index file은

search-key와 튜플에 대한 pointer로 구성되어있다

포인터는 A의 값들에 대한 튜플의 record ID의 포인터이고

search-key로 해당 조건을 만족하는 것을 찾으면

포인터를 타고 레코드에 접근하는 방식인 것이다

이런 구조를 data entry 혹은 index entry라고 부른다

그리고 이런 인덱스를 만드는

전형적인 방법은 tree와 hash가 있다

 

 

 

그렇다면 어떻게 하면 데이터를 빨리 찾을 수 있을까?

 

첫 번째 해결방법으로 full scanning이 있고

그리고 두 번째 해결방법으로는 A라는 컬럼에 대해

오름차순으로 sorting을 해서

이진탐색을 할 수 있다고 하자

 

 

 

index based access와 일반 full scanning access와의

비용 차이를 잠깐 비교해보자

 

A = 50000인 row를 찾고자하면

해당 file에 있는 record ID를 쫓아가서 row를 찾는다

data page가 100000개라고 하면

full table scan은 100000의 비용이 발생하지만

index table을 사용하면 3~4정도밖에 들지 않는다고 한다

또한 clustering factor라는 값이 있는데

그게 좋아지면 index의 성능이 좋아진다고한다

 

 

 

지금부터 모든 설명은 oracle을 기준으로 진행한다

아무튼 인덱스 테이블을 이용하면

4라는 비용을 통해 쿼리를 수행할 수 있다고 한다

 

우리가 CREATE INDEX를 하면 인덱스는

오른쪽 트리와 같은 B+ Tree 구조로 생성된다

거기서 key인 50000을 찾는 것이다

 

그럼 tree를 순회하면서 key인 50000을 찾아내고

찾아낸 leaf block에는

(50000, (5000, 10))과 같은 데이터가 있다

이말은 즉

A = 50000인 데이터는

#block 5000, #slot 10에 있다는 의미이다

따라서 해당 위치를 찾아 들어가서

데이터의 row를 가져온다

 

따라서 아래 database query 수행 결과를 보면

index table을 이용해서 수행하였고

위 예시는 point query였지만

range query시 ragne scan을 했다고 나온다

 

그리고 모두 다 buffer cache에 존재하여서

buffer cache에서 데이터를 가져와서

실제 디스크에는 접근하지 않았음을 알 수 있다

 

 

 

index query에는 point query와 같은 equality가 있고

range query와 같은 range search가 있다

따라서 두 가지 쿼리를 모두 잘 수행해야

index의 성능이 좋은 것이라고 할 수 있다

 

index의 목적은 수많은 데이터 중에서

쿼리 속도를 향상시키는 것이기 때문에

당연히 인덱스를 사용하면 쿼리 속도가 향상된다

하지만 당연히 trade off가 따르는데

index는 물리적 파일로 저장되기 때문에

별도의 storage가 사용된다

또한 insert, delete 시에 overhead가 발생한다

 

 

data entry k를 저장하는 방법에는

대표적으로 3가지가 있다

 

첫 번째는 찾고자하는 key인 k와 data record 자체를 저장하는 방식

두 번째는 k와 record ID만 저장하는 방식

마지막으로는 하나의 key값에 여러개의 record ID를 저장하는 방식이다

 

tree structured index는

range와 equality query를 모두 지원해주는데

ISAM과 B+ tree가 대표적인 방식이다

ISAM은 B+ tree의 전신으로

둘 다 tree based이고 ISAM은 트리의 구조가 바뀌지 않는

static 구조를

B+tree는 tree의 구조가 바뀌는 dynamic structure를 갖고있다

 

 

 

range search에 대해서 알아보자

 

예시에서 gpa가 3.0이 넘는 학생들을 찾아보려고한다

만약 데이터들이 정렬이 되어있다면

이진탐색을 통해서 첫번째로 조건을 만족하는 학생을 찾을 수 있고

그럼 조건을 만족하는 다른 학생들도 찾을 수 있다

이진탐색을 이용하면 시간복잡도는

log 2의 N이 된다

 

하지만 만약 sorting이 되어있지 않다고 하면?

우리는 create index를 통해

tree based로 정렬되어있지않은 page들을 정렬시킬 수 있다

따라서 index file은 정렬이 되어있고

이를 통해 쿼리를 빠르게 수행할 수 있는 것이다

 

 

 

먼저 첫 번째 방식은 ISAM에 대해서 알아보자

ISAMdms Index Sequential Access Method의 약자인데

아주 오래된 방식의 indexing이다

 

위 tree에서는 가장 아래 leaf pages에

실제 데이터의 record ID가 들어있다

 

ISAM은 트리의 구조가 변하지않는다

이게 무슨말이냐하면

만약 data insert가 발생한다면

우선 새로 추가된 데이터가 어디에 들어가면 좋을지

적절한 자리를 찾아간다

하지만 만약 적절한 데이터 페이지에 자리가 없으면

overflow page를 생성하여 데이터를 연결한다

 

따라서 overflow page가 과하게 생성되면서 탐색시 비효율이 발생할 수 있고

데이터가 delete가 되어서 데이터페이지에 빈 공간이 생긴다고해서

overflow page에 있던 데이터가 다시 돌아가는 경우는 없다

 

 

 

ISAM의 생성 과정을 간단하게 살펴보자

 

우선 leaf data pages에 들어갈 데이터들을

key를 기준으로 sorting한다

이렇게 sorting을 하기 때문에 range query도 가능하게 된다

 

그 다음 정렬된 leat data pages를 기준으로

recursive하게 tree 구조를 생성한다

 

그다음 생성한 Tree를 바탕으로 검색을 하거나

데이터가 새로 추가될 때는 빈공간에 삽입하거나

빈공간이 없다면 overflow page를 생성한다

 

데이터를 삭제할 때도 해당 데이터를 삭제한 다음

그 공간은 할당해제를 시켜준다

 

한마디로 그 어떤 과정에서도 중간에

tree structure가 변하지 않기 때문에

static tree structure이다

 

 

ISAM Tree의 예시이다

 

각 노드들은 2개의 entries를 가질 수 있다

data pages들을 sorting해서 sequential하게 나열하기 때문에

내 옆에 어떤 data page가 존재하는지 정보를 담을

next leaf page pointer를 가지고있을 필요가 없다

 

만약에 A = 46인 데이터를 찾고싶다면

우선 root로 들어간 다음

46은 40보다 크니까 오른쪽으로 가고

46은 51보다 작으므로 왼쪽으로 간다

그렇게 해서 40의 옆에 있는 46을 발견할 수가 있다

 

 

그런다음 위에서 본 구조에서

23, 38, 41, 42의 데이터를 넣어보겠다

 

비어있는 데이터페이지가 없기 때문에

overflow page를 생성하기 시작하고

계속해서 그 overflow page에 새로 추가되는 데이터를 담게 된다

 

사실상 tree에서 데이터를 찾기위해 중요한 것은

해당 tree가 얼마나 balance를 갖고있냐이다

이진 트리에서도 balance가 깨지는 순간

탐색 속도 차이가 많이 나게된다

 

따라서 이런 ISAM 구조는 계속해서 insert를 하다보면

tree의 balance가 깨지는 구조이고

이를 보완하기 위해 나온게 balanced tree인 B-Tree이다

 

 

 

이제 B+-Tree에 대해서 알아보자

balanced tree의 약자로 

tree에서 balance가 깨지는 것을 동적으로 막아서 방지하는 구조이다

 

 

B+-Tree의 장점으로는

automatic, local, reorganization 이런 것들이 있다고한다

 

하지만 단점으로는

평균적으로 index table의 3분의 2밖에 차있지않아서

space overhead가 발생한다고 한다

또한 삽입 삭제시 구조가 동적으로 변경되기 때문에

오버헤드가 추가적으로 발생한다

 

또한 인덱스가 클러스터링이 안되어있는 경우가 있는데

클러스터링이 잘 되어있는 인덱스는 성능이 매우 좋으나

클러스터링이 제대로 안되어있으면 성능이 저하될 수 있다

 

 

 

B+-Tree의 구조를 살펴보다

 

이렇게 root node가 있고 leaf nodes가 있다

root로부터 모든 leaf까지 가는 길의 길이는 모두 똑같고

이를 balanced라고 한다

 

 

위는 B+ Tree의 leaf node들을 쭈욱 나열해놓은 것이다

각각의 페이지들이 있고

지금 위 ppt에는 그림이 없지만

페이지 안에는 index entry가 4개씩 들어있다고한다

 

각 key인 k들은 정렬이 된 채로 저장되어있고

p는 각각 내부노드에서 자식 노드를 가리키는 포인터들이다

 

B+Tree의 order는 d라고 정의하고

m은 한 노드에 들어있는 key의 개수이고

D <= m <= 2d이다

 

운이 좋으면 전체 index의 꽉 차있을 수가 있는데

확률적으로는 보통 3분의 2정도가 차있다고 한다

 

root node는 0 <= m <= 2d이고

특별하게 key가 없어도 존재가능하다고 한다

 

 

index tree와 heap file을 한번 잘 보자

예시에서 column A의 값이 22인 것을 찾는다고 해보자

 

그럼 우선 root를 방문하게 될 것이다

그런 다음 22는 17과 24의 중간이기 때문에

17 <-> 24의 child pointer를 방문하게 된다

그럼 해당 child node에 22가 들어있는 것을 확인할 수 있다

 

하지만 인덱스의 성능은 클러스터링에 의해서 크게 갈린다

클러스터링이 잘되어있따는 소리는

heap file에 저장된 실제 데이터도

정렬이 잘 되어있다는 소리이다

 

하지만 클러스터링이 잘되어있을 떄와 잘 되어있지않을 때의 차이의

성능을 정확하게 예측하기는 힘들어서

주로 approximate를 많이 한다

 

 

 

B + Tree 알고리즘의 수도코드이다

그냥 한 번 훑어만봐도 좋다고 하셨다

 

 

 

위 오라클 예시에서 PK_EMP가

employ_number table의 search key값이다

위 경우는 클러스터링이 잘되어있는 편이라고 하셨다

 

 

 

위 쿼리의 결과값을 잘 보자

index block은 2304개

data entry는 100만개이고

2304개 중에서 leaf block의 개수는 2226개이다

 

branch row는 2225개

branch block은 5개이고

clustering factor는 10만이라고 하는데

이는 꽤 높은편이라고 한다

 

그런데 이 부분 좀 더 자세히 알아보고싶어서 gpt한테 물어봤더니

이 예시에서 clustering factor가 10만이면

아주 안좋은거라고 하는데..?

 

하지만 교수님께서는 좋은거라고 말씀하셨다..

난 교수님에 한표 ㅎㅎ..

 

 

 

아무튼 clustering factor가 10만이면 좋은거라고 하셨다

만약에 이 데이터들이 sorting이 하나도 안되어있고

shuffling이 되어있다면?

clustering factor는 100만정도가 나오고

이게 정말 최악이라고 한다

 

위 경우는 한 페이지에 레코드가 10개만 들어가기 때문에

최선은 10만, 최악은 100만이라고 한다

만약 한 파에지에 데이터 개수가 더 많아진다면

최악 clustering factor는 더 커지게 된다

 

 

point query와 range query에서 index를 탈 때

비용이 얼마나 드는지 알아보자

 

A column값의 범위는 최소가 1, 최대가 100만이라고 한다

그런데 우리가 찾는 범위는 1에서 20이라고 해보자

 

selectivity는 전체 중 쿼리가 접근하는 레코드의 비율을 말한다

따라서 총 100만 레코드중에서 20개만 접근하므로

selectivity는 100만분의 20이 된다

 

clustering factor는 인덱스 순서대로 데이터를 읽을 때

얼마나 랜덤하게 IO가 일어나는지를 나타내는 지표이다

값이 작을수록 데이터가 인덱스 순서대로 잘 정렬이 되어있다는 뜻이다

 

그렇다면 A컬럼이 1에서 100만까지 uniform하게 분포하고있다고 가정해보자

그렇다면 1에서 20까지의 row들은

selectivity * clustering factor = 2를 해서

2개의 block에 흩어져있을 가능성이 높게 된다

그러고 1이 더해져서

(... 사실 여기 설명을 잘 못들었다)

어떤 이유때문에 1이 더해져서 총 3개의 data page에 access한다고한다..

 

그런데 총 비용 모델이 2번의 인덱스에 접근하기 때문에(?)

(설명을 잘 못들어서 .. 이게 무슨소리인지..)

index의 최종 비용은 3 + 2를 해서 5라고 한다

 

CF가 10만이 아니고 100만이라고 하면

data page 개수가 2가 아니고 20이 된다

그래서 이럴 경우 총 index 비용은 24가 되어서

성능이 훨씬 더 안좋아진다고 한다

 

 

마지막 부분에 설명을 놓쳐서 정확하게 이해를 잘 못했다..

나중에 다시 제대로 공부를 해야할 것 같다

이번 시간은 여기서 마무리-!