[대학원] 면접준비 - 데이터베이스

Q) B-tree

Q) B+ tree, B* tree

[B-tree]

데이터베이스와 파일시스템에서 많이 사용하는 자료구조.

이진트리가 자식 노드가 최대 2개인 노드를 말하는 것이라면 B-tree는 자식노드의 개수가 2개 이상인 트리를 말한다. 또한 노드 내의 데이터가 1개 이상일 수가 있다. 노드 내 최대 데이터 수가 2개라면 2차 B-tree, 3개라면 3차 B-tree라고 한다. 1, 2, 3, ...M차 B-tree라고 한다. 

차수가 홀수인지 짝수인지에 따라 알고리즘이 달라진다. 

 

B-tree의 성립 조건에 대해서 알아보zㅏ

* 노드의 데이터 수가 n개라면 자식 노드의 수는 n+1개이다. 

* 노드의 데이터는 반드시 정렬된 상태여야 한다. 

* 노드의 자식노드의 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브트리에, 큰 값들은 오른쪽 서브 트리에 이루어져야 한다. 

* 루트 노드가 자식이 있다면 2개 이상의 자식을 가져야 한다. 

* 루트 노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가지고 있어야 한다. (4차부터 루트 노드를 제외하고 노드가 최소 2개 이상의 데이터를 가지고 있어야 한다.)

* Leaf 노드로 가는 경로의 길이는 모두 같아야 한다. 즉, Leaf 노드는 모두 같은 레벨에 존재해야 한다. 

* 입력 자료는 중복될 수 없다.

 

-탐색

B-tree는 이진트리와 마찬가지로 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 이루어져 있다. 

탐색하고자 하는 값을 root노드부터 시작해 하향식으로 탐색해 나간다. 

 

-삽입

차수에 따라 B-tree 알고리즘이 다르다. 

 

홀수(3차)

초기 삽입 시 root노드를 생성한다. 

1. 데이터를 탐색해 해당하는 Leaf 노드에 데이터를 삽입한다. 

2. Leaf 노드 데이터가 가득 차 있으면 노드를 분리한다. (if (노드 데이터 개수 == M(차수)))

- insert7에서 노드가 1, 5, 7로 가득찼다.

- 정렬된 노드를 기준으로 중간값을 부모 노드로 해서 트리를 구성한다.

3. 분리한 서브트리가 B-tree 조건에 맞지 않는다면 부모 노드로 올라가며 merge한다. 

- insert12에서 [9, 7, 12]를 서브트리로 분리하였으나 B-tree 조건에 맞지 않는다. 

(Leaf node가 모두 같은 레벨에 존재하지 않는다. )

Root 노드와 merge로 조건을 만족시킴

 

짝수

 

-삭제

Leaf노드인 경우와 Leaf노드가 아닌 경우로 나누어 진다.

B+트리

-모든 내부 노드(internel node)는 자료의 키값만 저장하고, 각 자료의 데이터는 오직 Leaf node에만 저장(리프 노드가 linked list로 구성됨)leaf 노드에 저장된 키와 동일한 키를 저장하는 내부 노드도 있을 수 있음.

- 각 leaf node에는 다음 형제 노드에 대한 포인터를 가지고 있어 중위 순회 없이도 순차적으로 접근 가능

 

B* Tree

-루트 노트가 아닌 노드는 최대 저장 공간의 2/3 이상의 자료가 저장되어야 함

(B-tree는 [m/2]-1 조건에 의해 최소 1/2 이상의 자료가 저장되어야 함.

- 노드에 저장되는 자료가 넘치는 경우(overflow), 일단 형제 노드들로 재분배시킴. 그리고 모든 형제 노드들이 가득 찬 경우에만 B-tree의 분할 연산을 수행(B-tree는 무조건 중간값을 가지는 자료를 부모 노드로 올려 보내고 분할하였음)

 

 

Q) Data inconsistency란?
자료 불일치
data consistency 데이터 일관성

Q) Data independence란?
자료 독립성
어느 단계의 스키마를 바꾸었을 때, 그 윗 단계의 스키마에 영향을 주지 않는 것을 가리킴
1) 물리적 자료 독립성
맨 아랫 단계인 물리적 단계의 스키마를 바꾸어도, 논리적 뷰 단계의 스키마는 영향을 주지 않고 응용 프로그램에도 주지 않음을 말함.
(응용 프로그램과 보조기억장치 같은 물리적 장치를 독립시킴으로써, 데이터베이스 시스템의 성능 향상을 위해 새로운 디스크를 도입하더라도 응용 프로그램에는 영향을 주지 않고 데이터의 물리적 구조만을 변경함)
2) 논리적 자료 독립성
가운데 단계인 논리적 단계의 스키마를 바꾸어도 그 윗 단계인 뷰 단계의 스키마에 영향을 주지 않고 그 결과 응용프로그램에도 영향을 주지 않음을 말함.
(응용 프로그램과 데이터베이스를 독립시킴으로써, 데이터의 논리적 구조를 변경시키더라도 응용 프로그램은 변경되지 않음)

Q) Data normalization이 무엇인가? 왜 필요한가?
[정규화(Normalization)]
* 함수적 종속성 등의 종속성 이론을 이용하여 잘못 설계된 관계형 스키마를 더 작은 속성의 세트로 쪼개서 바람직한 스키마로 만들어 가는 과정.
* 제 1정규형, 제 2정규형, 제 3정규형, BCNF형, 제 4정규형, 제 5정규형이 있으며, 차수가 높아질수록 만족시켜야 할 제약 조건이 늘어남.
* 정규화는 데이터베이스의 논리적 설계 단계에서 수행한다.
* 정규화는 논리적 처리 및 품질에 큰 영향을 미친다.

정규화의 목적
* 데이터 구조의 안정성을 최대화한다.
* 어떠한 릴레이션이라도 데이터베이스 내에서 표현 가능하게 만든다.
* 효과적인 검색 알고리즘을 생성할 수 있다.
* 중복을 배제하여 삽입, 삭제, 갱신 이상(anomaly)의 발생을 방지한다.
* 데이터 삽입 시 릴레이션을 재구성할 필요성을 줄인다.
* 속성들간의 종속 관계를 분석하여 1개의 릴레이션-> 여러 개의 릴레이션. 더 작은 테이블로 분해해가면서 종속성 제거

이상(Anomaly)의 개념
* 정규화를 거치지 않은 데이터베이스 내에 데이터들이 불필요하게 중복되어 릴레이션 조작 시 발생하는 예기치 못한 곤란한 현상
* attribute들 간에 존재하는 여러 종속 관계를 하나의 릴레이션에 표현하기 때문에 이상이 발생한다.

이상의 종류
삽입이상(insertion anomaly) : 릴레이션에 데이터를 삽입할 때 의도와는 관계없이 원하지 않은 값들도 함께 삽입되는 현상
삭제이상(deletion anomaly) : 릴레이션에서 한 튜플을 삭제할 때 의도와는 관계없는 값들도 함께 삭제되는 연쇄 삭제 현상
갱신이상(update anomaly) : 릴레이션에서 튜플에 있는 속성값을 갱신할 때 일부 튜플의 정보만 갱신되어 정보에 모순이 생기는 현상

Q) inner join과 outer join의 차이점은 ? outer join은 언제 사용하는가?
Q) 조인이란? 조인의 과정

 

*조인이란

- 한 데이터베이스 내의 여러 테이블의 레코드를 조합하여 하나의 열로 표현한 것.

- 따라서 조인은 테이블로서 저장되거나, 그 자체로 이용할 수 있는 결과 셋을 만들어 낸다. 

 

* 조인의 필요성

- 관계형 데이터베이스의 구조적 특징으로 정규화를 수행하면 의미 있는 데이터의 집합으로 테이블이 구성되고, 각 테이블끼리는 관계(Relationship)를 갖게 된다. 

- 이와 같은 특징으로 관계형 데이터베이스는 저장 공간의 효율성과 확장성이 향상되게 된다. 

- 다른 한편으로는 서로 관계있는 데이터가 여러 테이블로 나뉘어 저장되므로, 각 테이블에 저장된 데이터를 효과적으로 검색하기 위해 조인이 필요하다. 

 

* 조인의 종류

1) INNER JOIN

- 여러 애플리케이션에서 사용되는 가장 흔한 결합 방식. 기본 조인 형식

- 내부 조인은 조인 구문에 기반한 2개의 테이블(A, B)의 컬럼 값을 결합함으로써 새로운 결과 테이블을 형성한다.

 

 

2) OUTER JOIN

- 조인 대상 테이블에서 특정 테이블의 데이터가 모두 필요한 상황에서 외부 조인을 활용하여 효과적으로 결과집합을 생성할 수 있다. 

 

Q) DB와 file의 차이점은?

 

 

Q) 트랜잭션

[트랜잭션의 정의]
* 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미함.
* 데이터베이스 시스템에서 복구 및 병행 수행 시 처리되는 작업의 논리적 단위.
*하나의 트랜잭션은 commit되거나 rollback된다.
* 트랜잭션은 일반적으로 회복의 단위가 된다.

 

[트랜잭션의 특성]
Atomicity(원자성)
Consistency
Isolation
Durability

[출처]

시나공 정보처리기사 필기

untitledtblog.tistory.com/80

[파일구조] - B+ 트리

arisu1000.tistory.com/27718

B+ Tree (B+ 트리)

weejw.tistory.com/182

[File System] ::B* tree, B+ tree

m.blog.naver.com/PostView.nhn?blogId=kdy0573&logNo=220561840212&proxyReferer=https:%2F%2Fwww.google.com%2F

B트리 B+트리 B*트리

github.com/WeareSoft/tech-interview/blob/master/contents/network.md

WeareSoft/tech-interview