[Java] B-트리

 

 

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다.

 

 

 

 

 

 

 

 

데이터를 더 많이 담고 싶은데... 노드를 더 크게 만들어 보는거야

 

 

 

레드 블랙 트리나 B-트리 모두 2-3트리에서 나온 개념이다. 아무래도 대용량의 데이터를 다루기 위해 나온 자료구조이기 때문에 데이터베이스 분야에서 많이 쓰이는 형태라 할 수 있겠다.

 

 

 

 

---

 

B-트리

 

• 다수의 키를 가진 노드로 구성되어 다방향 탐색(Multiway Search)이 가능한 균형 트리
• 2-3 트리는 B-트리의 일종으로 노드에 키가 2개까지 있을 수 있는 트리
• B-트리는 대용량의 데이터를 위해 고안되어 주로 데이터베이스에 사용

 

 

노드에 수백에서 수천 개의 키를 저장하여 트리의 높이를 낮추자

 

 

B-트리의 정의

차수가 M인 B-트리는 다방향 탐색 트리이다.

• 모든 이파리는 같은 동일한 깊이를 갖는다.
• 루트가 아닌 각 노드의 자식 수는 [M/2] 이상 M 이하
• 루트의 자식 수는 2이상

 

B-트리의 노드는 최대 M-1개의 키를 저장할 수 있고, 최대 M개의 서브트리를 가질 수 있다.

 

---

 

탐색 연산

• B-트리에서의 탐색은 루트로부터 시작
• 방문한 각 노드에서는 탐색하는 키와 노드의 키들을 비교하여, 적절한 서브트리를 탐색
• 단, B-트리의 노드는 일반적으로 수백 개가 넘는 키를 가지므로 각 노드에서는 이진 탐색 수행

---

 

삽입 연산

• B-트리에서의 삽입은 탐색과 동일한 과정을 거쳐 새로운 키가 저장되어야 할 이파리를 찾는다.
• 이파리에 새 키를 수용할 공간이 있다면, 노드의 키들이 정렬 상태를 유지하도록 새 키를 삽입
• 이파리가 M-1개의 키를 가지고 있으면, M-1개의 키와 새 키 중에서 중간값이 되는 키(중간 키)를 부모로 올려보내고, 남은 M-1개의 키를 1/2씩 나누어 각각 별도의 노드에 저장<분리(Split) 연산>

 

 

 

e.g.  45 삽입하기

 

루트에서 45가 20과 50의 사잇값. [25, 30, 35, 40]을 가진 이파리에 도달. 하지만 이미 4개의 키를 가지고 있어서 45 수용 불가.

따라서 분리 연산을 통해 25, 30, 35, 40, 45 중에서 중간키인 35를 부모인 루트로 올려보낸다. 하지만 부모또한 노드가 4개, 따라서 수용 불가.

5, 10, 20, 35, 50 중에서 중간키인 20을 부모로 올려보낸다. 루트의 부모는 없기 때문에 새로운 루트 생성 후 20 저장. 새 루트가 만들어질 때 높이 1 증가

 

 

 

 

---

 

삭제 연산

• B-트리에서의 삭제는 항상 이파리에서 이루어진다.
• 삭제할 키가 내부 노드에 있으면, 중위 선행자나 중위 후속자를 삭제할 키와 교환한 후 이파리에서 삭제 수행
• 삭제는 이동(Transfer) 연산과 통합(Fusion) 연산 사용
• 이동 연산 : 이파리에서 키가 삭제된 후웨 키의 수가 [M/2] - 1보다 작으면, 자식 수가 [M/2]보다 작게 되어 B-트리 조건을 위반. 이때 노드의 좌우의 형제 중에서 도움을 줄 수 있는 노드로부터 1개의 키를 부모를 통해 이동

 

 

e.g. 5 삭제하기

 

 

---

 

통합 연산

키가 삭제된 후 underflow가 발생한 노드 x에 대해 이동 연산이 불가능한 경우, 노드 x와 그의 형제를 1개의 노드로 통합하고, 노드 x와 형제의 분기점 역할을 하던 부모의 키를 통합된 노드로 끌어내리는 연산

 

e.g. 7 삭제하기

 

 

 

---

 

B-트리의 확장

B* - 트리

• B*-트리는 B-트리로서 루트를 제외한 다른 노드의 자식 수가 2/3M~M이어야 한다. 즉, 각 노드에 적어도 2/3 이상이 키들로 채워져 있어야 한다는 것.
• B-트리에 비해 B*-트리는 공간을 효율적으로 활용한다.

 

B+ - 트리

• 실제로 가장 널리 활용되는 B-트리이다.
• 키 만을 가지고 B-트리를 구성, 이파리에 키와 관련(실제) 정보를 저장한다.
• 키로 구성된 B-트리는 탐색, 삽입, 삭제 연산을 위해 관련된 이파리를 빠르게 찾을 수 있도록 안내해주는 역할만 수행한다.
• 전체 레코드를 순차적으로 접근할 수 있도록 연결 리스트로 구현한다.

 

 

---

성능 분석

• B-트리에서 삽입이나 삭제 연산의 수행 시간은 각각 B-트리의 높이에 비례. 차수가 M이고 키의 개수가 n인 B-트리의 최대 높이는

• B-트리는 키들의 비교 횟수보다 디스크와 메인 메모리 사이의 블록 이동(Transfer) 수를 최소화 해야한다.
• B-트리의 최고 성능을 위해서는 1개의 노드가 1개의 디스크 페이지에 맞도록 차수 M을 정한다.
• 실제로 B-트리들은 M의 크기를 수백에서 수천으로 사용한다.
  • M = 200이고 n = 1억 이라면 B-트리의 연산은 4개의 디스크 블록만 메인 메모리로 읽어 들이면 처리가 가능하다.
• 성능 향상을 위해 루트는 메인 메모리에 상주

 

 

응용

• B-트리, B+ -트리는 대용량의 데이터를 저장하고 유지하는 다양한 데이터베이스 시스템의 기본 자료구조로 활용
• Windows 운영체제의 파일 시스템 : HPFS(High Performance File System)
• 매킨토시 운영체제의 파일 시스템 : HFS(Hierarchical File System)과 HFS+
• 리눅스 운영체제의 파일 시스템  : ReiserFS, XFS, Ext3FS, JFS
• 상용 데이터베이스 : ORACLE, DB2, INGRES와 오픈소스 DBMS인 PostgreSQL에서 사용