[database] B+Tree Index의 insertion과 deletion (+hash indexing)

본 게시글은

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

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

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

---

이전 시간에 배운 tree based index structure에서

B+Tree에 대해서 좀 더 자세히 살펴보자

우선은 inserting과 deletion이다

 

 

저번 시간에 DB index가 어떻게 값을 찾는지 배웠다

각 data는 search key인 50000과

뒤에 몇 번째 block의 몇 번째 slot에

해당 record가 존재하는지를 의미한다

 

따라서 tree에서 검색해야할 key를 찾고

해당 record를 찾아가는 구조를 갖고있다

 

따라서 data가 새로 insertion되너가 deletion될 때

B+Tree의 경우 tree의 구조가 변경되게된다

 

 

B+Tree에 data가 insert 될 때 어떻게 바뀔까?

 

우선 새로 추가할 데이터는 루트를 따라서

추가되어야할 자리를 찾는다

만약 거기에 자리가 있으면 그냥 그대로 데이터를 넣으면 되지만

만약에 데이터가 들어갈 자리가 없을 경우

노드를 분할하거나, 상위 index의 노드로 전파된다고 한다

이 과정은 root까지 갈 수 있어서

루트가 분할되게되면 tree의 height가 증가한다고 한다

 

이 과정을 이후에 자세히 살펴보자

 

 

 

 

예를 들어서 15라는 새로운 데이터를 넣으려고한다고 하자

그럼 root부터 시작해서 14와 16사이로 들어가야하는데

이 경우는 빈 공간이 있기 때문에

아무것도 바꾸지않고 데이터 삽입이 가능해진다

 

하지만 만약에 8이라는 데이터를 넣고싶다면?

해당 페이지에 데이터 entry가 가득 차있어서

8을 새로 넣을 수가 없다

 

이런 경우 저번 시간에 배웠던 ISAM은 overflow page를 생성한다

하지만 B+Tree는 그렇게 하지않고 해당 페이지를 2개로 쪼갠다

 

그렇다면 2와 3은 원래 페이지에 남겨두고

5, 7과 새로 들어갈 8을 새로 할당받은 페이지에 copy를 한다

그런 다음에 5를 위 노드로 copy up해서 새로 올리려했지만

root도 지금 꽉 차서 새로운 5가 들어갈 자리가 없다

 

그럼 root에서 또 한개를 copy up해서 올린 뒤

새로운 root로 만들고 split up을 해준다

이렇게 recursive한 구조로 계속해서 split해주는 것이다

 

 

 

따라서 결과적으로는 이렇게 된다

8을 넣기 위해서 5가 들어있던 node를 split하고

5를 위로 copy up을 하려했으나 root에도 자리가 없었어서

root를 split한 후 17을 copy up해서 새로운 root로 만들어주었다

그런다음 5와 13은 왼쪽으로, 24와 30은 오른쪽으로 갔고

5의 자식으로는 아까 split up해주었던 8이 포함된 노드가 있다

 

따라서 처음보다 height가 1개 늘어난 3이 되었다

 

 

이제 deletion이다

deletion 부분은 간단하게만 살펴보고 넘어가겠다

실제로 deletion이 들어온다고 하더라도

데이터를 안지우고 냅두는 경우가 대부분이라고한다

그 이유는 deletion을 할 때 발생하는 런타임 오버헤드를

줄이기 위함이라고 한다

 

 

B+Tree에서 lnsertion과 deletion은

log f N 정도의 비용이 소모된다고한다

 

그리고 앞에서도 계속 말했지만

B+Tree의 경우 최소 50% 정도만 차있고

평균적으로는 3분의 2만 차있다

 

 

실제 B+Tree를 간단하게 살펴보자

order는 100이고 67%정도만 차있다

인덱스의 루트노드는 메모리의 핵심데이터라고한다

 

 

다음으로 hashing 기반의 index를 살펴보자

hash는 인기있는 인덱싱 기법 중 하나이다

hash 함수를 활용해서 인덱싱을 하는데

가장 쉬운 해시함수는 모듈러 함수라고 한다

따라서 나머지값을 key로 받아서 쭉쭉 나누는 것이다

 

이러한 hashing은 light weight하다는 장점이 있지만

치명적인 단점은 range query의 경우

굉장히 수행이 복잡해진다는 점이다

이러한 이유로 보통 B+Tree 보다는 general하지 않지만

나중에 join 기법중에서 해시조인이 나오기 때문에

해시라는 개념 자체는 매우 중요하다

 

 

 

B+Tree는 주로 OLTP에 특화된 인덱스이다

 

B+Tree와 hashing이외에 다른 인덱싱 기법으로는

bitmap과 R-Tree가 있는데

bitmap은 0과 1로 구분하는 인덱싱 기법을 말한다

위 ppt 예시에서

남자와 여자의 경우

그리고 rating의 경우 bitmap으로 인덱싱을 해놓은 것을 볼 수 있다

만약에 남자이면서 rating이 3인걸 찾는다하면

bitmap을 읽어서 AND AND 연산을 하면 된다

OLAP의 입장에서는 이러한 bitmap indexing이 꽤나 유용하다

 

또 마지막으로 R-Tree라는 인덱싱 기법이 있는데

공간데이터같은 (..나의 전공)

2차원, 3차원 데이터를 다룰 때 사용되는 인덱싱 기법이다

 

 

이번 수업의 내용은 짧은데 ..

마지막 슬라이드이다

 

교수님께서는 결국 AI 시대의 모든 데이터들은

궁극적으로 벡터 인덱스로 바뀔 것이라고 하셨다

 

지금까지 우리가 자세히 배운 인덱싱 기법들은

정확한 데이터를 찾는 symbolic한 기법이라고 하면

벡터는 exact matching이 아니다

가장 근접한 n개에 대해서 approximate하게 값을 찾는 기법이고

이걸 하게 해주는 것으로는 벡터 데이터베이스가있다