B쁠러쓰마이나쓰Tree

B+Tree? B-Tree?

Beeeeee-Tree

데이터에 순차적인 접근을 효율적으로 할 수 있게 해주는 자료구조임.

바이너리 트리와 다르게 노드가 세 개 이상의 자식을 가질 수 있음.

각 노드에는 key가 있고, 오름차순 정렬됨.

각 키마다 자식 노드 두 개에 대한 참조를 가지게 되고,

왼쪽 자식노드보다는 크고,

오른쪽 자식노드보다는 작아야함.

한 노드가 x개의 키를 가지고 있다면,

자식 노드는 키를 x+1개를 가질 수 있음.

 

 

B+ 트리는?

리프노드에서만 데이터를 저장한다. 즉, 리프 노드가 아닌 키들은 그림처럼 아래로 쭈우욱 내려와서 리프노드로 복제된다. (9, 11, 13, 16, 30, 38). 포인터를 통해 모든 값을 순차적으로 순회할 수 있게 된다. 리프가 연결되어있기 떄문에 레인지 쿼리에 효율적이다.

 

 

 

예시?

DB에서 인덱싱을 사용하지 않으면, 타겟 레코드를 찾기 위해 모든 레코드를 읽음.

인덱스를 생성하면 컬럼별로 field값이 key가 되는 B-Tree를 생성한다.

where = 'value' 쿼리의 경우 B-Tree 탐색하면 빠르게 해당 key를 찾을 수 있다.

column > 'value'와 같은 조건이 붙으면 B+Tree가 더 효울적일 것임...

그럼 맨날 인덱스 쓰면 되겟냉?

맛난건 살찐다. 인덱싱에는 오버헤드가 따른다. ㅠㅠ

다음과 같이 테스트 해 봤을때, 적어도 PostgreSQL의 경우,

Cost에 따라서 엔진이 더 효율적인 스캔 방법을 선택하게 된다

 

 

 

 

 

 이렇게 작은 데이터셋에 

seqscan을 off 해줘야 강제로 index를 사용할 수 있다

 

 

 

 

이렇게 인덱스를 사용하면

 

 

컴포짓 인덱스인거 확인

cost=0.13 어쩌구 확인

 

 

 

 

 

Seq Scan이 ON이면, Seq scan시 cost가 위보다 훨씬 작은 것을 알 수 있고, 자동으로 Seq scan 선택된 것 확인.

 

Bottom Line

이야기가 옆구리로 샜네...

B-Tree와 B+Tree를 혼용해서 칭하거나 DB에서 인덱싱에 혼용한다고도 이야기 하는데,

어떤걸 사용하느냐 보다는, 어떤 걸 인덱싱에 사용하는지, 어떤걸 레코드 저장에 사용하는지의 뉘앙스 차이인 것 같다. (예를 들어 PostgreSQL에는 B+Tree를 인덱싱으로 사용하지만 데이터는 테이블에 저장되는데 InnoDB 엔진(MySQL, MariaDB)은 노드에 직접 데이터를 저장한다).

 

이제 뭔지 알았으니

그런건 DB깎는 장인들께 맡겨두자...