cs 스터디 4주차

4주차

6. 인덱스

해시테이블, B/B+tree로 구현 가능한데

해시테이블은 잘 안 쓴다고 함.

 

그 이유는, 해시 테이블은 등호(=) 연산에 최적화되어있기 때문이다. 데이터베이스에선 부등호(<, >) 연산이 자주 사용되는데, 해시 테이블 내의 데이터들은 정렬되어 있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내에 찾을 수가 없다. 

 

 

B tree는 이진탐색트리의 일종으로 data가 한쪽으로 쏠리는 걸 막고 일정한 level을 유지하게끔 설계된 트리임.

B+ tree는 기존의 B tree보다 좀 더 발전돼서 나온 것.

 

data 조회는 빠른데 삽입/삭제/갱신 이런 거 하려면 좀 복잡함.

이것도 이해가 필요하기보단 그냥 rule을 받아들이고 그대로 따라가면 됨.

 

B tree

 

떨어져있지 않은 직사각형 세트가 노드고 그 안에 진한 노란색이 다음 노드를 가리키는 포인터, 가운데 있는 숫자가 key 값, 그 아래에 있는 게 data

 

몇가지 rule이 있음.

 

 

1. node의 key의 수가 k개라면, 자식 node의 수는 k+1개이다. 

2. node의 key는 반드시 정렬된 상태여야 한다. 

3. 자식 node들의 key는 현재 node의 key를 기준으로 크기 순으로 나뉘게 된다. 

4. root node는 항상 2개 이상의 자식 node를 갖는다. (root node가 leaf node인 경우 제외) 

5. M차 트리일 때, root node와 leaf node를 제외한 모든 node는 최소 ⌈M2⌉⌈M2⌉, 최대 MM개의 서브 트리를 갖는다. 

6. 모든 leaf node들은 같은 level에 있어야 한다.

• 노드는 최대 M개 부터 M/2개 까지의 자식을 가질 수 있습니다.
• 노드에는 최대 M−1개 부터 [M/2]−1개의 키가 포함될 수 있습니다.

 

구체적인 과정은 아래 블로그에 compact하게 정리돼있어서 그냥 직접 들어가서 보는 게 빠름.

내가 한 번 더 정리할 게 없음. 아래 포스팅 내용 중에 헷갈리는 부분이 있으면 답변 가능함.

 

[DB] 10. B-Tree (B-트리)

 

https://rebro.kr/167

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

b+ 트리

data를 리프노드에만 저장하며 리프노드끼리는 linked list로 연결돼있다는 특징이 있다.

리프노드로 내려오기까지 노드들에는 다음 노드로 향하는 포인터만 저장이 돼있고

key값은 중복될 수 있다.

 

기존의 B-Tree는 어느 한 데이터의 검색은 효율적이지만, 모든 데이터를 한 번 순회하는 데에는 트리의 모든 노드를 방문해야 하므로 비효율적이다. 이러한 B-Tree의 단점을 개선시킨 자료구조가 B+Tree이다. 

 

1. leaf node를 제외하고 데이터를 저장하지 않기 때문에 메모리를 더 확보할 수 있다. 따라서 하나의 node에 더 많은 포인터를 가질 수 있기 때문에 트리의 높이가 더 낮아지므로 검색 속도를 높일 수 있다. 

 

2. Full scan을 하는 경우 B+Tree는 leaf node에만 데이터가 저장되어 있고, leaf node끼리 linked list로 연결되어 있기 때문에 선형 시간이 소모된다. 반면 B-Tree는 모든 node를 확인해야 한다. 

 

반면, B-Tree의 경우 최상의 경우 특정 key를 root node에서 찾을 수 있지만, B+Tree의 경우 반드시 특정 key에 접근하기 위해서 leaf node까지 가야 하는 단점이 있다.  

 

인덱스에서 B-Tree 대신 주로 B+Tree를 사용하는 이유는 뭘까?

해시 테이블에서 언급했듯이 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생할 수 있다. 따라서 B+Tree의 Linked list를 이용하면 순차 검색을 효율적으로 할 수 있게 된다.  

 

B+Tree의 검색 과정은 B-Tree와 동일하다. 반면 B+Tree의 삽입과 삭제 과정은 약간의 차이가 있다. 기본적으로 B+Tree의 삽입과 삭제는 항상 leaf node에서 일어난다. 

 

 

 

7. 트랜잭션과 교착상태

데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위

 

[ 트랜잭션 ]

• 트랜잭션: DBMS에서 데이터를 다루는 논리적인 작업의 단위
• DB에서 데이터를 다룰 때 장애가 일어난 경우 데이터를 복구하는 작업의 단위가 된다.
• DB에서 여러 작업이 동시에 같은 데이터를 다룰 때가 이 작업을 서로 분리하는 단위가 된다.
• 트랜잭션은 전체가 수행되거나 또는 전혀 수행되지 않아야 한다.(All or Nothing)

https://mangkyu.tistory.com/30

[Database] 8. 트랜잭션, 동시성 제어, 회복

• 트랜잭션의 특징 (ACID)
  • Atomicity, Consistency, Isolation, Durability

https://rebro.kr/162

[DB] 9. 트랜잭션(Transaction) - (1) 특성, ACID, 연산, 상태

1. 원자성 (Automicity) 

 

트랜잭션을 구성하는 연산은 반드시 모두 실행이 되거나 혹은 아예 실행되지 않아야 한다. 즉, 하나의 트랜잭션에서 일부 연산만 실행되면 안 된다.

따라서 실행 도중에 오류가 발생하여 작업을 완료하지 못하였다면, 트랜잭션 전체를 취소하여 수행 이전으로 돌아가야 한다. 

 

 

2. 일관성 (Consistency)

 

트랜잭션이 완료된 상태에서도 트랜잭션 이전의 상황과 동일하게 데이터의 일관성이 있어야 한다. 데이터에 모순이 있어서는 안 된다. 

은행 송금 기능을 생각해보면, 트랜잭션 수행 이전의 송금자와 수금자의 잔액 합이 수행 후에 달라지거나, 혹은 잔액을 나타내는 자료형이 정수형에서 문자열로 바뀌는 등의 모순이 발생하면 안 된다. 

 

 

3. 독립성, 격리성 (Isolation)

 

트랜잭션은 다른 트랜잭션에 간섭을 주거나 받지 않고 독립적으로 수행되어야 한다. 

둘 이상의 트랜잭션이 병행 실행되는 경우, 현재 수행 중인 트랜잭션이 완료되기 전에 현재 트랜잭션이 생성한 중간 연산 결과를 다른 트랜잭션이 접근하면 안 된다. 

독립성을 통해서, 사용자들은 여러 트랜잭션이 동시에 수행되고 있는 것처럼 느끼면서도 정확한 결과를 얻을 수 있게 된다. 

 

 

4. 지속성 (Durability)

 

트랜잭션이 성공적으로 완료되었을 때 그 결과는 영구적으로 반영되어야 한다. 시스템의 장애가 발생하더라도 결과는 데이터베이스에 그대로 남아있어야 하며, 지속성을 보장하기 위해서 회복 기능이 필요하다. 

 

 

• 트랜잭션 상태
  • Active, Parital Commit, Commited, Failed, Aborted

 

1. 활성화(Active) : 트랜잭션이 작업을 시작하여 실행 중인 상태

 

2. 실패(Failed) : 트랜잭션에 오류가 발생하여 실행이 중단된 상태

 

3. 철회(Aborted) : 트랜잭션이 비정상적으로 종료되어 Rollback 연산을 수행한 상태

 

4. 부분 완료(Partially commited) : 트랜잭션의 마지막 연산까지 실행하고 commit 요청이 들어온 직후의 상태. 최종 결과를 데이터베이스에 아직 반영하지 않은 상태.

 

5. 완료(Commited) : 트랜잭션이 성공적으로 종료되어 commit 연산을 실행한 후의 상태

 

 

• 트랜잭션 명령어
  • Commit, Rollback

1. Commit 연산

 

Commit 연산은 하나의 트랜잭션이 성공적으로 종료된 후, 데이터베이스가 일관된 상태를 유지할 때 갱신 연산이 완료되었다고 트랜잭션 관리자에게 알려주고 결과를 최종적으로 데이터베이스에 반영하는 연산이다. 

 

2. Rollback 연산

 

Rollback 연산은 하나의 트랜잭션이 비정상적으로 종료되어 데이터베이스의 일관성을 잃었을 때 트랜잭션이 지금까지 실행한 연산의 결과가 취소되고 트랜잭션 수행 이전의 상태로 돌아가는 연산이다. 

Rollback을 하는 경우엔 해당 트랜잭션을 재시작하거나 폐기한다. 

 

 

• 트랜잭션 발생 가능 문제
  • Dirty Read Problem

작업중인 트랜잭션 2가 작업을 Rollback한 경우 트랜잭션 1은 무효가 된 데이터를 읽게 되고 잘못된 결과를 도출한다.

한마디로, rollback을 했는데도 기존의 걸 계속 읽는 것

무효가 된 데이터를 읽게되어 발생하는 문제

 

• Non-repeatable Read Problem

트랜잭션 1이 데이터를 읽고 트랜잭션 2가 데이터를 쓰고(Update) 트랜잭션 1이 다시 한번 데이터를 읽을 때 생기는 문제

한 자원에 대해서 읽다가 정보를 update하고 다시 읽어보니 달라져있는 것, (달라졌으니) 말 그대로 다시 읽을 수가 없다는 거겠지.

 

• Phantom Read Problem

트랜잭션 1이 데이터를 읽고 트랜잭션 2가 데이터를 쓰고(Insert) 트랜잭션 1이 다시 한번 데이터를 읽을 때 생기는 문제

바로 전에는 없었던 값이 읽히게 되는데 이를 유령데이터 읽기라고 합니다.