1조 물리적 데이터베이스 미션

B+ 트리 인덱싱

• B-tree 의 등장 배경

  • 디스크에 데이터 구조를 효율적으로 저장하기 위해 발명됨.
  • Balanced-Tree : 이진 탐색트리가 삽입 순서에 따라 편향 트리가 될 가능성이 존재 → Log(n) → N
  • AVLTree / Red-Black / B-tree
  • AVLTree / Red-Black 트리는 각각의 노드가 1개의 데이터를 가지고있고, B-tree는 한 노드에 여러개의 데이터를 가질 수 있어서 높이가 훨씬 낮기때문에 Disk IO가 더 적게 일어난다.

• B-tree 의 동작 방식

  1. 구조:
     • 각 비리프 노드는 최대 m개의 자식을 가질 수 있습니다 (m은 B-트리의 차수).
     • 실제 데이터는 리프 노드에 저장됩니다.
  2. 주요 특성:
     • 모든 리프 노드는 같은 깊이에 있습니다.
     • n개의 자식을 가진 노드는 n-1개의 키를 포함합니다.
     • 루트를 제외한 모든 노드는 최소 반만큼 채워져 있어야 합니다.
     • 루트 노드는 리프가 아닌 경우 최소 2개의 자식을 가집니다.
  3. 검색 과정:
     • 루트에서 시작하여 키를 비교하며 적절한 자식 노드로 이동합니다.
     • 리프 노드에 도달할 때까지 이 과정을 반복합니다.
  4. 삽입 과정:
     • 적절한 리프 노드를 찾아 새 요소를 삽입합니다.
     • 노드가 가득 차면 분할하고, 중간 키를 부모 노드로 올립니다.
     • 필요시 이 과정을 루트까지 반복합니다.
  5. 삭제 과정:
     • 요소를 리프 노드에서 제거합니다.
     • 노드가 최소 채움 조건을 위반하면 재분배 또는 병합을 수행합니다.
     • 필요시 이 과정을 루트까지 반복합니다.

• B-tree와 B+ tree의 차이점

  • B-Tree는 각 Node 자체에 실질적인 값 혹은 값에대한 참조값이 들어간다.
  • B+Tree는 각 Node에는 루트노드의 키값만 존재하고, 실질적인 값 혹은 참조값은 리프노드에 링크드리스트 형태로 연결되어있다.

  B-트리 (B-Tree)
  B-트리는 균형 이진 탐색 트리의 일반화된 버전으로, 노드가 여러 개의 자식 노드를 가질 수 있습니다. 모든 노드는 여러 개의 키와 자식 노드를 가질 수 있으며, 자식 노드는 키의 값에 따라 분리됩니다.
  
  특징
  내부 노드와 리프 노드: B-트리에서 모든 노드는 키와 자식을 가질 수 있습니다. 리프 노드는 데이터를 저장하며, 내부 노드 또한 데이터를 직접 저장할 수 있습니다.
  데이터 저장: 데이터는 트리의 모든 노드에 분포될 수 있으며, 내부 노드와 리프 노드 모두에 저장됩니다.
  탐색: 특정 키를 찾기 위해 루트에서 리프 노드까지 탐색하며, 경로 중간의 내부 노드에서 데이터를 찾을 수 있습니다.
  디스크 접근 최적화: B-트리는 디스크 접근의 최소화를 위해 설계되어 있으며, 대용량 데이터베이스에서 사용하기에 적합합니다.
  B+트리 (B+Tree)
  B+트리는 B-트리의 확장 버전으로, B-트리의 일부 문제를 해결하고 더 나은 성능을 제공하기 위해 고안되었습니다. B+트리에서는 내부 노드와 리프 노드의 역할이 분리되어 있습니다.
  
  특징
  내부 노드와 리프 노드: 내부 노드는 오직 탐색을 위한 인덱스 역할을 하며, 실제 데이터는 리프 노드에만 저장됩니다. 따라서 내부 노드는 오직 자식 노드로의 포인터와 키 값만을 가집니다.
  데이터 저장: 모든 실제 데이터는 리프 노드에만 저장되며, 이들은 정렬된 상태로 유지됩니다. 각 리프 노드는 다음 리프 노드를 가리키는 포인터를 가지며, 이를 통해 리프 노드들이 연결 리스트 형태를 이룹니다.
  탐색 효율성: 탐색은 내부 노드를 통해 리프 노드로 빠르게 도달하며, 리프 노드에서는 정렬된 데이터를 빠르게 접근할 수 있습니다.
  범위 쿼리: 리프 노드가 연결 리스트 형태로 연결되어 있기 때문에, 특정 범위의 데이터를 연속적으로 접근하는 데 매우 효율적입니다.
  주요 차이점
  데이터 저장 위치:
  
  B-트리: 데이터가 내부 노드와 리프 노드 모두에 저장될 수 있습니다.
  B+트리: 데이터는 오직 리프 노드에만 저장됩니다. 내부 노드는 인덱스 역할만 합니다.
  리프 노드 간 연결:
  
  B-트리: 리프 노드 간에 특별한 연결이 없습니다.
  B+트리: 리프 노드가 연결 리스트 형태로 연결되어 있어, 범위 쿼리에 매우 효율적입니다.
  탐색 경로:
  
  B-트리: 탐색 도중에 내부 노드에서 데이터를 찾을 수 있습니다.
  B+트리: 모든 탐색은 리프 노드까지 내려가야 하며, 실제 데이터는 리프 노드에서만 찾을 수 있습니다.
  디스크 I/O 효율성:
  
  B-트리: 내부 노드에 데이터가 저장될 수 있어, 일부 경우 디스크 접근 횟수가 줄어들 수 있습니다.
  B+트리: 모든 데이터가 리프 노드에 집중되기 때문에, 디스크 접근 패턴이 더 예측 가능하고, 범위 쿼리에 특히 효율적입니다.

Clustered Index란?

인덱스의 키 값으로 정렬된 데이터

• Clustered Index의 동작방식
• 테이블을 저장하는 다른 방식도 있을까?
• 물리적으로 테이블을 저장하는 다양한 방법

MySQL과 InnoDB

• InnoDB 란 무엇인가?
• InnoDB 에서 create database -> create table 을 할 때 일어나는 일을 설명해 보세요.
• InnoDB 외에 어떤 스토리지 엔진들을 사용할 수 있는가? 특징은?

힙 테이블: 인덱스가 없는 테이블

데이터 저장 방식

row store: 레코드로 저장.

column store: 같은 컬럼만 들어있음. OLAP 에 유리함.

Indexing

• MySQL 에서 지원하는 인덱스의 종류와 용도에 대해 설명해 보세요.
• MySQL 로 지도정보를 저장하고 싶습니다. 어떻게 해야 할까요?

데이터베이스 일반

• Oracle, MS-SQL, PostgreSQL 에서 테이블과 레코드를 저장하는 방식은 어떤 것들이 있는가?
• 그룹으로 위 주제에 대해 학습하고 학습정리결과를 댓글로 달아 주세요.

trie, T-트리