dongineer

Consistency 

분산 환경을 공부하다보면 CAP를 마주하게 된다. 

우선, 분산처리환경의 CAP는 Consistency, Availability, Partition tolerance이고, 트랜잭션의 ACID는 Atomicity, Consistency, Reliability, Isolation, Durability이다. 이글은 각 개념보다는 C에따른 A?.. 위주로 정리하고자 한다. 

ACID의 C와 CAP의 C는 같은 Consistency지만, 의미가 다른 Consistency이다. 

ACID의 일관성(Consistency)는 트랜잭션이 완료되었을 때 기존의 제약을 위반하지 않아야한다는 일관성이고, 

CAP의 일관성(Consistency)는 모든 요청에대해 최신 데이터, 또는 에러를 응답받아야한다는 일관성이다. 

ACID의 일관성을 예로 들어보면, 은행에서 출금 후 잔고가 음수이면 안된다. 음수일 경우 트랜잭션은 실패해야하고, rollback되어야 한다. 즉 기존의 제약을 위반하지 않는 데이터로 일관돼야한다. 

CAP의 일관성을 예로 들어보면, 부산에서 돈을 출금했을때, 일산에서 잔고를 확인하나, 서울대입구에서 잔고를 확인하나 최신에 업데이트된 값을 보여주어야한다. 

먼저 CAP이론은 한계가 명확하다.

가장 아래에 참고한 영상 링크를 걸어두었는데 그 영상의 제목은 You don't need CP, you don't want AP, and you can't have CA다.

극단적으로 CAP 중 2개를 만족하는 구조는 불가능, 혹은 장점이 없다. 따라서 더나은 CAP이론의 해석은 "가용성과 일관성은 어느정도 상충관계에 있지만 극단적으로 둘 중 하나만 선택해야하는건 아니다." 이다. 

CP와 AP 그 사이 어디쯤으로 선택해야하는데 CP가 얼마나 우선될지, AP가 얼마나 우선될지 그 정도를 선택하는게 중요하다.

 또한 파티션이 없는 상황을 설명하지 못한다는 것이다. 파티션이 없는 상황에서도 분산 시스템은 상충하는 특성들이 있고, 장애 상황만큼이나 정상 상황에서 시스템이 어떻게 동작하는지도 중요하다.

CAP의 이러한 한계로 PACELC 이론이 나왔는데 마지막에 간단하게 정리해보자.. 

Eventual Consistency 

분산 시스템을 구축하다보면 C와 A 중 우선순위를 선택할때가 온다.

Eventual Consistency는 고가용성을 보장하는 일관성 모델이다. 

jodong2라는 서버와, dongineer라는 서버가 있다고 가정하고, 그 두개는 별도의 데이터베이스를 사용한다고 가정하자. 

클라이언트가 요청을 보내고, jodong2라는 서버에 데이터베이스의 데이터가 수정되었다고 하자. 이때 dongieer의 데이터베이스에 해당 데이터와는 내용이 다를 수 있다. 

이때 다른 클라이언트들이 해당 데이터를 읽기위한 요청을 보낸다면 

1. 모든 서버가 동일한 데이터를 갖도록 동기화하는 동안 클라이언트의 접근을 막는 경우 - 가용성 X
2. 어떤 클라이언트는 최신화된 jodong2의 데이터를, 어떤 클라이언트는 최신화되지 않은 dongineer의 데이터를 보여주는 경우 - 일관성 X

두가지 경우가 있다. 이때 2번이 Eventual Consistency 방식이다. 2번의 경우에는 언젠가 동기화 작업이 완료되면, 모든 클라이언트가 동일한 데이터를 볼 수 있다. 단기적으로는 전체적인 일관성을 잃을지 몰라도, 결과적으로 전체적인 일관성을 보여주는 모델이 Eventual Consistency 모델이다. 

위의 그림에서 Node A는 상위노드이고, B,C는 복제본이다. Node A에서 X 데이터에 대해 쓰기 작업이 이뤄지는 중이라도, 혹은 동기화가 되지 않아도 항상 X 데이터를 읽을 수 있다. 이때 B는 동기화되고, C는 동기화 되지 않았을 경우에도, 각자 갖고 있는 데이터중 최신 데이터를 보여준다. 이때 각 데이터는 차이가 발생할 수 있지만, 언제나 접근 가능하다는걸 보여준다. 

인터넷 DNS(도메인 이름 시스템)는 eventual consistency 모델이 사용된 시스템의 예로 잘 알려져 있습니다. DNS 서버가 항상 최신의 값을 반영하는 것은 아니며, 이러한 값들은 인터넷상의 수많은 디렉터리에서 캐싱되고 복제됩니다. 수정된 값을 모든 DNS 클라이언트와 서버에 복제하려면 어느 정도의 시간이 소요됩니다. 하지만 DNS 시스템은 인터넷의 근간을 이루는 요소로 자리잡은 매우 성공적인 시스템입니다. DNS는 가용성이 매우 높으며 엄청난 확장성이 증명되었고, 인터넷 전체에서 수천만 대 기기의 이름 조회를 가능하게 하고 있습니다.

Strong Consistency 

반대되는(?) 개념으로 Strong Consistency가 있다. 

1. 모든 서버가 동일한 데이터를 갖도록 동기화하는 동안 클라이언트의 접근을 막는 경우 - 가용성 X

 위에서 보여준 예시중 1번과 관련있는 Consistency 모델로 기본적인 관계형 데이터베이스가 그 대표적인 모델이다. 

Strong Consistency 모델은 모든 클라이언트에게 동일한 데이터(일관성)를 보여주기 위해 가용성을 어느정도 포기한 모델인데, 관계형 데이터베이스는 데이터베이스의 여러 인스턴스가 항상 동일한 데이터를 갖도록 한다. 이때 동기화 작업 중 lock이 걸릴 수 있으며 이는 가용성에 문제가 생긴다. 따라서 설계하기 나름이지만, 기본적인 관계형 데이터베이스는 일관성을 우선시한 대표적인 모델이다. 

PACELC

CAP이론은 위에서 말한 한계점이 있다. 

PACELC는 CAP이론을 대체하기 위해 나온 이론이다. CAP이론은 정상 상황을 서술하지 못한다는 문제를 해결하기 위해 나왔다. 서버가 Partition 된 상황이라면 A(Availability) 와 C(Consistency)를 골라야하고, E(Else) L(latency) 와 (Consistency)를 골라야한다. 

 분산 DB에서 파티션(Partition)일때 Availability를 선택하여 모든 DB에 반영하기보다는, 접근 가능한 노드에만 반영하면 PA, 반대로 모든 DB 반영되는걸 기다리며 Consistency를 선택한다면 PC이다. 

 정상상황 (Else) 일 때는 빠르게 처리하기 위해 몇몇 DB에만 반영하며 Latency를 선택하면 EL, 모든 DB에 적용하여 Consistency를 선택하면 EC이다. 이때 Latency를 선택한다는 것은 지연시간을 줄이는것을 선택하는 것이다. 

 프로젝트를 진행하며 MSA를 공부하고 있다. 내가 담당한 부분 중 하나는 인스타그램의 스토리와 유사한 기능이다. 

 알림과 유사한듯 유사하지 않은 스토리 기능은 일관성이 크게 중요하지 않은 기능이다 ! 

참고 

https://cloud.google.com/datastore/docs/articles/balancing-strong-and-eventual-consistency-with-google-cloud-datastore?hl=ko#what-is-eventual-consistency 

https://www.oracle.com/kr/database/what-is-a-relational-database/

https://velog.io/@soongjamm/Eventual-Consistency-%EB%9E%80

https://www.youtube.com/watch?v=hUd_9FENShA

SQL Injection 제목이 곧 내용이다. 

 보이지 않는 손 같이 멋지고 섹시한 네이밍센스는 이과, 공대에서 찾기 힘들다. 대부분 이름이 내용이거나 만든사람 이름이다. 

SQL Injection이란 악의적인 사용자가 보안상의 취약점을 이용하여, 임의의 SQL 문을 주입하고 실행되게 하여 데이터베이스가 비정상적인 동작을 하도록 조작하는 행위이다. 

-- tmi 

 OWASP(Open Web Application Security Project)라는 프로젝트가 있다.

 애플리케이션 보안에만 전념하는 여러 커뮤니티 그룹의 조직이 있는데 이중 가장 큰 그룹이 OWASP이다. 

 주로 웹에 관한 정보노출, 악성 파일 및 스크립트, 보안 취약점 등을 연구하며, 2013년, 2017년, 2021년 10대 웹 애플리케이션의 취약점 OWASP TOP 10을 발표했다. 선정 기준은 웹 애플리케이션 취약점 중에서 공격 빈도가 많고, 보안상 영향을 크게 줄 수 있는 가성비 좋은 취약점들이다. 13년과 17년에선 1위, 21년엔 3위를 기록한 취약점이 SQL Injection이다. 

실제로 2017년 여기어때도 SQL Injection으로 인한 개인정보 유출사건이 발생했고 피해가 엄청났다고 한다. 

SQL Injection은 보안과목에서 다뤄야하지 않나 싶어서 주제 바꾸자고 말하려다가.. 수업내용도 나오고... 그래도 알아두면 좋을거같아서 입꾹닫고 포스팅한다. 

 아무리 가성비 좋은 SQL Injection이라고 해서 아무거나 생각나는데로 쿼리를 막 넣는게 아니다.

여러가지 방법, 종류가 있는데 종류에 대해 알아보고 대응 방안에 대해 알아보자 

SQL Injection 종류 

Error based SQL Injection (논리적 에러를 이용한 SQL Injection)

논리식에 허점을 이용한 SQL Injection이다. 가장 많이 쓰이며, 대중적인(?) 공격기법이다. 

아래는 일반적으로 로그인할 때 가장 많이 사용되는 sql 구분이다.  

SELECT * FROM Useres WHERE id='input1' and password = 'input2'

여기서 사용자가 input1에 아래와 같은 인풋을 넣는다고 가정해보자.

' OR 1=1 --

input1을 처리한 쿼리는 아래와 같다.

SELECT * FROM Users WHERE id='' OR 1=1 -- ' AND password = 'input2'

--를 이용하여 input1 뒤의 문장을 전부 주석처리하고, OR 1=1을 넣음으로서 해당 조건은 모두 True가 된다.

따라서 위의 쿼리는 아래의 쿼리와 결과가 항상 같다. 

SELECT * FROM Users

매우 간단한 input1인데 결론적으로 Users 테이블에 있는 모든 정보를 조회하게 되고, 가장 먼저 만들어진 계정으로 로그인에 성공하게 된다. 심지어 대부분 관리자 계정을 가장 처음 만들기 때문에 계정에 관리자 계정으로 로그인 될 확률이 크다. 

Union based SQL Injection (Union 명령어를 이용한 SQL Injection)

SQL에서 Union 키워드는 두개의 쿼리문에 대한 결과를 통합해서 하나의 테이블로 보여주게 하는 키워드이다. 

정상적인 쿼리문에 Union 키워드를 사용하여 인젝션하면, 원하는 쿼리문을 실행할 수 있게 된다. 

설명보다 쿼리부터 확인하는게 이해하기 쉬워보인다.

-- 게시글 조회
SELECT * FROM Board WHERE title LIKE '%INPUT%' OR contents '%INPUT%'

위와 같은 쿼리가 있다. 게시글의 제목이나 내용에 input과 같은게 있으면 보여달라는  검색하는 쿼리이다. 

여기서 사용자가 INPUT으로 아래와 같은 쿼리를 넣는다고 가정해보자. 

'
UNION 
SELECT null,id,passwd FROM Users --

INPUT을 처리한 쿼리는 아래와 같다.

SELECT * FROM Board WHERE title LIKE '%' 
UNION 
SELECT null,id,passwd FROM Users -- %' OR contents '%INPUT%'

이 쿼리문의 수행 결과는 보드의 타이틀과 아무거나 매치되는 결과와 유저의 id와 passwd를 함께 보여주는 테이블이 보여지게 된다. 인젝션이 성공하게 된다면, 사용자의 개인정보가 게시글과 함께 화면에 보여지게 될 것이다.

 물론 패스워드를 평문으로 데이터베이스에 저장하지는 않겠지만 인젝션이 가능하다는 점에서 보안 위험에 노출되어 있다. 

예시에서 null을 넣어주었는데 UNION 연산은 컬럼 수를 맞춰줘야하기때문에 null을 넣었다. 

컬럼수, 테이블의 컬럼 이름 등 테이블의 구조를 필요로하는 경우가 많은데 이또한 SQL Injection으로 획득이 가능하다. 

Blind SQL Injection  (Boolean based SQL)

데이터베이스로부터 특정한 값이나 데이터를 전달받지 않고, 단순히 참과 거짓 정보만 알 수 있을때 사용한다.

로그인 폼에 SQL Injection이 가능하다고 가정했을때 서버가 응답하는 로그인 성공과 로그인 실패 메세지를 이용하여, DB의 테이블 정보 등을 추출할 수 있다. 즉,  사용자의 데이터보단 데이터베이스, 테이블의 정보를 알아내는 방법이다. 

다시 한 번 로그인할때 자주 사용되는 SQL을 보자 

SELECT * FROM Users WHERE id = 'input1' AND password = 'input2'

그리고 역시 input1에 내가 원하는 sql을 삽입한다. 

abc123' AND ASCII(SUBSTR(SELECT name FROM information_schema.tables WHERE table_type='base table' limit 0,1)1,1)) > 100 --

위와같은 긴 인풋을 넣는다. (MySQL 가정) 

사용자는 임의로 회원가입한 abc123이라는 아이디와 함께 주입한다. AND 뒤에 오는 SELECT 구문은 MySQL에서 테이블명을 조회하는 구문으로 limit키워드를 통해 하나의 테이블만 조회하고, SUBSTR 함수로 첫글자만, 마지막으로 ASCII를 통해서 ascii값으로 변환해준다. 만약에 조회되는 테이블명이 Users라면 'U'자가 ascii값으로 조회될 것이고, 뒤의 100이라는 숫자 값과 비교하게 된다. 거짓이면 로그인 실패가 될 것이고 참이라면 로그인에 성공할 것인데, 참이 될 때 까지 뒤의 100이라는 숫자를 변경해가며 비교한다. 공격자는 이 프로세스를 자동화 스크립트를 통해 단기간내에 테이블 명을 알아낼 수 있다.  

Blind SQL Injection  (Time based SQL)

얘도 마찬가지로 서버로부터 특정한 응답대신 참, 거짓의 응답을 통해서 데이터베이스의 정보를 유추하는 기법이다. 

사용되는 함수는 MySQL 기준 SLEEP과 BENCHMARK이다. 

다시 로그인하는 SQL

SELECT * FROM Users WHERE id = 'input1' AND password = 'input2'

삽입할 쿼리

abc123' OR (LENGTH(DATABASE())=1 AND SLEEP(2)) -- 
-- SLEEP이 치환처리 되어있다면 BENCHMARK() 함수 사용
abc123' OR(LENGTH(DATABASE())=1 AND BENCHMARK(1000000,AES_ENCRYPT('hello','goodbye'));

위의 쿼리는 데이터베이스의 길이를 알아내는 방법으로 SLEEP(2)가 동작할때까지 (LENGTH(DATABASE())=1에서 숫자 1을 변경해가며 시도한다. (AND연산 특성상 LENGTH(DATABASE())가 1이라면 SLEEP(2)가 동작할것이고 아니라면 동작하지 않는다.)

만약 SLEEP이라는 단어가 치환처리 되어있다면 또다른 방법으로 BENCHMARK나 WAIT함수를 사용할 수 있다. 

치환처리는 뒤에 대응방안에서 알아보자.

Stored Procedure SQL Injection (저장된 프로시저에서의 SQL Injection)

저장 프로시저(Stored Proceduere)은 일련의 쿼리들을 모아 하나의 함수처럼 사용하기 위한 것이다. 

공격에 사용되는 대표적인 저장 프로시저는 MS-SQL에 있는 xp_cmdshell로 윈도우 명령어를 사용할 수 있게 된다. 단, 공격자가 시스템 권한을 획득해야 하므로 공격난이도가 높으나, 공격에 성공한다면 서버에 직접적인 피해를 입힐 수 있는 공격이다. 

Mass SQL Injection (다량의 SQL Injection 공격)

 기존 SQL Injection과 달리 한번의 공격으로 다량의 데이터베이스가 조작되어 큰 피해를 입히는 것을 의미한다. 

 데이터베이스에 악성스크립트를 삽입하고, 사용자들이 변조된 사이트에 접속 시 좀비 PC로 감염되게 하며 해당 좀비 PC들을 DDos공격에 사용한다. 

대응 방안

입력값에 대한 검증

SQL Injection에서 사용되는 기법과 키워드는 엄청나게 많다.

사용자의 입력값에 대한 검증이 필요한데, 서버단에서 화이트리스트 기반으로 검증해야한다. 즉, 가능한 키워드를 리스트로 만들어 검증해야한다. 불가능한 키워드를 리스트로(블랙리스트) 만들어 검증할 경우 보다 많은 키워드를 등록해야하며, 하나라도 빠지면 공격 당할 수 있기 때문이다.  

 여기서 화이트리스트에 포함되지 않거나, 블랙리스트에 포함된다면, 문자를 치환하는 방법을 많이 쓴다. 이때 공백으로 치환하는 경우가 종종있는데 공백으로 치환하는 방법은 취약한 검증 방법이다.

예를들어 공격자가 SESELECTLECT 를 입력한다면 중간의 SELECT가 공백으로 치환되며 다시 SELECT가 완성된다. 이러한 경우의 수를 전부 처리하기보다 공백대신 공격키워드와는 의미없는 단어로 치환하는 방법이 적절하다. 

Prepared Statement 구문 사용 

 Prepared Statement 구문을 사용하게 되면, 사용자의 입력 값이 데이터베이스의 파라미터로 들어가기 전에 DBMS가 미리 컴파일 하여 실행하지 않고 대기한다. 

그 후 사용자의 입력값을 문자열로 인식하게 하여 공격쿼리가 들어간다하더라도, 사용자의 입력은 의미 없는 단순 문자열이 된다. 

SELECT * FROM Users WHERE id = 'input1' AND password = 'input2'

에서 input1과 input2를 처리한 쿼리문을 입력받은 뒤 컴파일하는것이 아니라, 쿼리문을 미리 컴파일해놓고, input1과 input2를 처리한다면 뒤의 내용이 -- 를 통해 주석이 될 일도, 다른 쿼리문이 삽입 될 일도 없다. 

괜히 교수님이 prepared statement쓰라는게 아니다. 이내용과 아래 Error Message 노출금지 내용이 없었으면 아마 SQL Injection말고 주제 하자고 했을 수도 있다. 

Error Message 숨기기

 공격자가 SQL Injection을 수행하기 위해서는 데이터베이스의 정보(테이블 명, 컬럼명 등)가 필요하다. DB에서 에러발생시 따로 처리해주지 않았다몀ㄴ, 에러가 발생한 쿼리문과 함께 에러에 관한 내용을 반환해주는데 이 내용을 바로 보여준다면 테이블 명, 컬럼명, 쿼리문이 노출될 수 있다. 따라서 사용자에게 보여줄 수 있는 페이지를 별도로 만들거나, 메세지박스를 따로 만드는것이 좋다.

(에러 처리는 꼭 할 수 있어야해요~~)

https://security04.tistory.com/171

  요약해보면

 위의 블로그 내용은 엄청나게 많은 예시가 있다. 사용자가 input으로 넣으면 위험한 내용들이다. 따라서 얘네의 입력을 막거나, 검증된 입력만 받을 수 있도록 리스트를 작성해야한다. 

그리고 교수님말 잘듣자 :) 

데드락? 교착상태?

 OS에서 중요하게 다루는 문제로 데드락, 교착상태가 있다. OS에서 데드락을 안다는 가정하에 OS의 데드락을 간략히 설명하고 데이터베이스의 데드락을 보자.

 OS의 DeadLock, 교착상태란 둘 이상의 프로세스가 자원을 점유하고 다른 프로세스가 점유중인 자원을 요구하면서 무한정 기다리는 현상이다. 이런 이기적인 프로세스들은 상호배제, 점유대기, 비선점, 환형대기 4가지 조건하에 태어난다.

 해결방법으로는 위의 4가지 조건 중 하나라도 만족하지 않게 애초에 방지하거나, 교착상태가 발생할거 같으면 자원을 할당하지 않고 회피하거나, 교착상태가 발생하든말든 냅두다가 발생하면 탐지하고 회복하는 방법이 있다. 

데이터베이스에서의 데드락은 언제 왜 발생하고 어떻게 해결할까? 

데이터베이스의 교착상태도 OS와 똑같다. OS의 이기적인 프로세스가 문제라면 DB에는 이기적인(?) 트랜잭션이 문제다.

(==트랜잭션도 하나의 프로세스다.)

DeadLock, 교착상태란 둘 이상의 프로세스가 자원을 점유하고 다른 프로세스가 점유중인 자원을 요구하면서 무한정 기다리는 현상이다. 이런 이기적인 프로세스들은 상호배제, 점유대기, 비선점, 환형대기 4가지 조건하에 태어난다.

라고 위에서 말했는데 여기서 자원 -> 데이터, 프로세스-> 트랜잭션으로 바꾸기만 하면 DB에서의 데드락이 발생하는 상황을 이해하기 쉽다. 

자원, 점유하는 방법, 프로세스는 OS에서 알아보고 데이터베이스에서는 트랜잭션이 뭔지, 데이터를 왜 점유하는지, 어떻게 점유하는지, 어떻게 해결하는지 알아보자.

트랜잭션 

https://dana-study-log.tistory.com/entry/DB-%ED%8A%B8%EB%9E%9C%EC%9E%AD%EC%85%98%EA%B0%9C%EB%85%90%ED%8A%B9%EC%84%B1%EC%97%B0%EC%82%B0%EC%83%81%ED%83%9C?category=1081271

 트랜잭션이란 ACID를 만족하여 무결성을 보장하며 데이터의 상태를 바꾸는 작업의 단위이다. 예를들어 INSERT, DELETE, UPDATE 등 DML은 트랜잭션으로 볼 수 있다. DML은 데이터의 상태를 변경하고, DB는 자동으로 Commit을 실행하여 변경된 내역을 데이터베이스에 반영한다. 실패한다면 데이터의 상태가 변경되기전으로 돌아가는 작업인 Rollback을 수행한다. 

 트랜잭션의 이기적인 부분은 ACID의 Isolation이다. 

Isolation 조건을 만족하기 위해 트랜잭션은 동시에 접근하는것을 제어하고 여기서 데드락이 발생할 수 있다. 

 트랜잭션하면 흔히 나오는 예시로 입출금이 있다. 내 계좌에서 돈을 빼고(UPDATE) 뺀만큼 상대방 계좌에 돈을 넣는(UPDATE) 작업은 UPDATE 두 개가 모두 성공한 뒤 Commit해야한다. 둘 중 하나라도 실패할 경우 Commit되지 않고 트랜잭션이 시작하기전으로 Rollback한다. 반드시 둘 다 성공해야만 Commit이 진행된다. 

 여기서 추가로 Isolation(고립성, 독립성)을 위한 예시를 들어보면,

동언이형은 전재산이 1000원이다.
난 동언이형한테 3000원을 송금했다. 
그리고 안채는 데이터베이스에 내 송금작업이 Commit되기전에 동언이형한테 5000원을 송금했다. 

1. 내 돈을 입금하며 동언이형의 계좌에 잔고를 (1000원 + 3000원)으로 UPDATE한다.
2. 그리고 Commit되기 전에 안채가 동언이형한테 5천원을 송금했다.
3. 이때 안채가 송금작업을 수행할 당시 바라본 동언이형의 잔고는 천원이고 (1000원 + 5000원)으로 UPDATE하게 된다. -> Dirty Read
4. 내 송금작업에 대해 Commit을 진행한다. ( 동언이형 잔고 1000원 + 3000원 ) 
5. 안채의 송금작업에 대해 Commit을 진행한다. ( 동언이형 잔고 1000원 + 5000원 ) -> 내 송금작업에 대한 갱신손실 

입금과 출금이 2번씩 UPDATE가 4번 발생했으며 모든작업이 Commit 됐음에도 동언이형은 3천원을 도둑맞았다.

이러한 문제(갱신손실)를 포함해서 다양한 문제를 해결하기위해 트랜잭션은 Isolation을 만족해야한다. 

Isolation

 트랜잭션은 동언이형의 3천원을 지키기위해 데이터를 고립(Lock)시켜서 데이터에 동시에 접근하는 것을 제어한다.

만약 동시에 접근하는것이 제어되지 않는다면 위의 예시를 포함하여 다음과 같은 상황에서 문제가 발생할 수 있다. 

즉 트랜잭션은 Isolation 을 만족하기위해 동시접근을 제어하여 위의 문제점들을 방지할 필요가 있다.

동시접근을 제어하는 방법으로는 트랜잭션스케줄링, LOCK이 있다. 우리는 데드락이 목적이니 스케줄은 대충하고 LOCK에대해서 자세히 알아보자. 

트랜잭션 스케줄

LOCK

트랜잭션들이 동일한 데이터 항목에 대해 임의적 병행 접근을 하지 못하도록 제어하는 방법이다. 

Lock연산은 아래와 같은 조건들을 지키며 수행된다. 

• 트랜잭션 T가 데이터 항목 D에 대해 READ(D) or WRITE(D)연산을 수행하려면 반드시 LOCK(D) 연산을 수행해야한다. 
• 트랜잭션 T가 실행한 LOCK(D)에 대해서는 트랜잭션 T가 종료되기 전 반드시 UNLOCK(D)연산을 수행해야한다. 
• 트랜잭션 T는 다른 트랜잭션T2에 의해 이미 LOCK(D)이 걸려있는 D에 대해 다시 LOCK(D)를 수행하지 못한다. ->(S-LOCK끼리는 가능)
• 트랜잭션 T가 D에 LOCK(D)를 걸지 않았다면, 트랜잭션 T는 D에대해 UNLOCK(D)를 수행하지 못한다. 

공유락 Shared - LOCK (S-LOCK)

• Shared Lock를 설정한 트랜잭션은 데이터 항목에 대해 읽기 연산만 가능하다. 
  • 트랜잭션 T가 데이터항목 D에 대해 S-LOCK(D)을 설정하면 T는 읽기 연산만 가능하다. 
• 하나의 데이터 항목에 대해 여러개의 트랜잭션이 Shared Lock 할 수 있다. 
  • 트랜잭션 T1이 데이터항목 D에 대해 S-LOCK(D)을 설정한 경우에, 트랜잭션 T2도 데이터항목 D에대해 S-LOCK(D)를 설정할 수 있다. 
• S-LOCK(D)가 걸려있다면 S-LOCK을 건 트랜잭션 포함 다른 트랜잭션에서도 읽기연산은 수행가능하다. 
  • 트랜잭션 T1이 데이터항목 D에 대해 S-LOCK(D)를 설정한 경우, T1을 포함한 다른 트랜잭션들도 읽기 작업이 수행가능하다. (쓰기작업은 불가능하다.)

배타락 Exclusive-LOCK(X-LOCK)

• X-LOCK을 설정한 트랜잭션T1은 데이터항목 D에 대해 읽기와 쓰기 연산 모두 가능하다. 
• 하나의 데이터항목에대해 하나의 트랜잭션만 X-LOCK을 걸 수 있다. 
• 동시에 여러개의 트랜잭션이 X-LOCK을 걸 수 없다. 
  • 트랜잭션 T1이 X-LOCK(D)을 걸었다면 T1이 UNLOCK(D)하기 전에 T2에서는 X-LOCK(D)를 수행할 수 없다.
  • T2는 D에대해 X-LOCK(D)작업이 불가능하다.

잠금규칙

• 트랜잭션은 READ(D) 연산을 실행할 때 S-LOCK(D)이나 X-LOCK(D) 중 하나를 실행해야한다.
• WRITE(D)를 수행하려면 X-LOCK(D)를 실행해야한다. 
• 어떤 LOCK이든, 어떤 연산이든 작업 종료 후에는 UNLOCK(D) 연산을 실행해야 한다.
• UNLOCK(D)는 S-LOCK(D) 혹은 X-LOCK(D)가 수행된 후에만 실행될 수 있다. 
  • 즉, LOCK 없는 UNLOCK없고 UNLOCK없는 LOCK없다. 

잠금단위

잠금단위란 잠금의 대상이 되는 데이터 객체의 크기로 레코드의 필드값, 레코드, 물리적 입출단위인 디스크부터 테이이나 데이터베이스까지 하나의 잠금 단위로 설정할 수 있다. 

• 잠금 단위가 클수록 동시성(병행성)수준은 낮아지고, 동시성 제어 기법이 간단해진다. 
• 잠금 단위가 작을수록 동시성(병행성)수준은 높아지고, 동시성 제어 기법이 복잡해진다. 

따라서 여러개의 잠금 단위를 설정하고 필요에따라 사용할 수 있어야한다. 

교착상태, 데드락 

드디어 교착상태, 데드락이다. 이걸위해 LOCK이고 트랜잭션이고 설명했다. 

LOCK은 트랜잭션의 고립성을 만족시키기 위해, 또 동언이형의 3천원을 지키기 위해 꼭 필요하다. 

따라서 LOCK은 대부분의 DBMS에서 사용하는 방식이다. 하지만 큰 한계가 존재한다. 

트랜잭션 TA가 x에 X-LOCK를 걸고, 해당 LOCK이 끝나기 전에 y에도 X-LOCK(y)를 걸려고 한다.(하나의 트랜잭션이 여러개의 데이터에 접근하는 상황)

하지만 y는 트랜잭션 TB가 S-LOCK을 걸어놓은 상태고 트랜잭션 TB는 y에 대한 S-LOCK(y)를 끝내기 전에 데이터 x에 S-LOCK(x)를 걸려고 한다. 

x는 TA가, y는 TB가 LOCK을 걸어놨고, TA는 y에대한 UNLOCK을, TB는 x에대한 UNLOCK을 기다린다. 트랜잭션 둘 중 하나가 양보하지 않으면 한없이 기다리며 이때 교착상태, 데드락이 발생한다.

 Isolation을 만족시키지 않으면 동언이형은 3천원을 도둑맞고 Isolation을 만족시키기위해 LOCK을 걸자니 교착상태, 데드락이 발생할 수 있다.

위의 예시 상황은 데드락의 네가지 조건들을 만족한다.

• 상호배제  : 데이터의 한 항목에대해 함께 작업할 수 없고 독점적으로 사용한다. 
• 점유대기  : 트랜잭션은 데이터에 LOCK을 걸고 다른 데이터의 UNLOCK을 기다린다. 
• 비선점.    : 트랜잭션은 다른 트랜잭션이 걸어놓은 LOCK을 UNLOCK할 수 없다. 
• 환형 대기 : 각 트랜잭션이 서로 순환적으로 다른 트랜잭션의 UNLOCK을 기다린다.  

네가지 조건 모두 만족해야 데드락이 발생하고 이중 하나라도 만족하지 않으면 데드락이 발생하지 않는다. 

데이터베이스에서 데드락 해결하기 

DB에서 데드락을 해결하는 방법으로는 4가지 조건 중 하나라도 만족하지 않게 애초에 방지하거나, 교착상태가 발생할거 같으면 LOCK하지 않고 회피하거나, 교착상태가 발생하든말든 냅두다가 발생하면 탐지하고 회복하는 방법이 있다. 

방지기법

각 트랜잭션이 실행되기 전 미리 필요한 모든 데이터를 LOCK한다.

 위의 예시와는 다르게 TA는 시작할때 필요한 데이터를 파악하고, x와 y에 모두 LOCK을 실행한다. 그럼 중간에 TB가 y에 LOCK을 시도할때 TA의 UNLOCK을 기다려야하고 TA는 y에대한 데이터를 사용한뒤 UNLOCK하면 TB가 사용할 수 있다. 따라서 데드락을 애초에 방지할 수 있다.

 하지만 필요한 모든 데이터를 LOCK해야 하므로 병행성이 떨어진다. 즉, 현재 y데이터는 사용하지 않고 x에 대한 작업만 수행하고 있음에도 y에 접근할 수 없다. 

SET LOCK_TIMEOUT문을 통해 일정시간이 지나면 트랜잭션, 쿼리를 취소한다. 

 데드락인 데이터가 있다면 그 데이터에 대한 작업은 오랜시간 대기하게 될 것이므로, 일정시간이 지나면 취소하는 방법이다.

간단하게 방지할 수 있지만 일정시간 기다려야하므로 근본적인 해결책이 될 수 없다. 

회피기법 

데이터에 LOCK을 실행할 때 Time Stamp를 활용해서 교착상태가 일어나지 않도록 회피하는 방법이다. 

방지기법에서의 단점들때문에 실제로는 회피기법이 주로 사용된다.

Wait-Die방식

 트랜잭션 A가 트랜잭션 B에 의해 잠금된 데이터를 요청할 때 트랜잭션 A가 먼저 실행된 트랜잭션이라면 B가 끝날때까지 대기한다. 

 트랜잭션 A가 트랜잭션 B에 의해 잠금된 데이터를 요청할 때 트랜잭션 A가 늦게 실행된 트랜잭션이라면 포기하고 나중에 다시 요청한다. 

Wound-Wait방식

 트랜잭션 A가 트랜잭션 B보다 먼저 실행된 트랜잭션이라면, 데이터를 선점(Wound)한다. 

 트랜잭션 A가 트랜잭션 B보다 늦게 실행된 트랜잭션이라면, B가 끝날때까지 대기한다. 

낙관적 병행 제어 기법

낙관적 병행 제어 기법은 트랜잭션이 실행되는 동안 검사를 수행하지 않고 트랜잭션의 계산이 마무리 된 후에 데이터에 문제가 있다면 RollBack, 없다면 commit 하는 방법이다. 

낙관적 병행 제어 기법에서는 판독 -> 확인 -> 기록 단계를 따르는데 확인 단계를 거친 트랜잭션만 기록 단계를 수행할 수 있다. 

다시 동언이형의 사라진 3천원을 보자. 

내 잔고 + 동언이형 잔고 + 안채 잔고의 값은 일정해야한다. 총합에서 3천원이 사라진것은 문제고 이러한 문제는 판독 -> 확인 과정에서 문제가 발생시킨다. 그럼 RollBack되고 내 잔고에 다시 3천원이 돌아올 것이다. 

정확히 표현하면 트랜잭션은 다른 사본을 만들어 관리하고, 트랜잭션에서 갱신(UPDATE)은 사본에 대해 실행한다. 그리고 확인단계에서 트랜잭션 실행 결과가 직렬 가능성위반을 체크한다. 예를 들어 동시에 쓰기작업을 진행했다면, 문제가 있는 작업이다. 쓰기작업이 동시에 이뤄지지 않았다면 확인단계를 통과하고 Commit하며, 확인단계를 통과하지 못했다면 RollBack한다. 

Index란?

Index(색인) : 책 속의 낱말이나 구절, 또 이에 관련한 지시자를 찾아보기 쉽도록 나열한 목록

 이 단어는 어디있구나, 이 내용은 어디있구나 를 알려주는 페이지로
책이 100페이지가 있다면 위의 이미지와 같은 페이지가 1~2페이지는 존재할것이다.

대충 책의 1%가 인덱스 페이지라고 가정하자.

 책 전체를 안훑어보고 1%만 훑어봐도 원하는 내용의 위치를 찾을 수 있다. 대충 찾는 속도가 100배 빨라졌다.

 그럼 만약 책이 1000000011장으로 구성되어있다면 10000000장은 인덱스 페이지로 쓰일 것이다. 10000000장 중에 내가 원하는 내용의 위치가 적힌 페이지를 찾는건 100배 빨라졌다하더라도 답답할 따름이다.

 따라서 인덱스 페이지 내에서도 원하는 내용이 적힌 페이지가 명시된 부분을 찾기 쉽게 할 필요가 있다. 위의 이미지를 다시 한 번 보자. 단어들은 알파벳순으로 정렬되어 있다. 내가 찾는 단어가 Bae정현이라면 B로 시작하는 부분만 찾으면 된다. 알파벳 별로 분포가 균일하다면 대충 100배에서 추가로 26배 빨라졌다. 2번째 알파벳도, 3번째 알파벳도 순서대로 정리 되어있겠지만 처음 알파벳까지만 봐도 2600배 빨라졌다.

책의 페이지 중 1%를 희생해서 원하는 정보를 빠르게 찾을 수 있도록 도와주는 것이 인덱스의 역할이다.

DB에서의 Index

Q1-1) DB작업을 할 때 속도가 느린 상황입니다. 무엇을 고려할껀가요? 
A1-1)  DB 작업을 할 때 속도저하가 발생하는 대부분의 작업은 SELECT문, 조건 검색 WHERE절에서 발생합니다. 먼저 SQL문이 효율적으로 작성되어 있는지 확인한 뒤 문제가 없다면 Index를 고려해볼 수 있습니다.

Q1-2) Index가 뭔가요 ? 
A1-2) 인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료 구조입니다.

Q1-3) Index는 어떻게 속도를 높여주나요 ? 
A1-3) 별도의 저장공간을 할당하여 데이터의 위치정보를 Value값, 찾고자 하는 정보(Column)를 Key 값인  Key - Value 형태로 저장하고 Key값을 기준으로 정렬하여 (== B Tree를 만들어) 탐색을 빠르게 해줍니다. 

Q1-4) 그럼 모든 컬럼에 Index 테이블을 만들어주면 데이터베이스는 속도가 빨라지나요?? 
A1-4) 아닙니다. 인덱스 테이블은 항상 정렬된 상태를 유지해야 하기 때문에 읽기작업이 아닌 쓰기, 수정작업이 많이 필요한 테이블에 인덱스가 존재할 경우 성능이 저하됩니다. 

 데이터베이스의 인덱스도 책의 인덱스와 같은 메커니즘이다.

 원하는 데이터의 위치를 빠르게 찾아 읽을 수 있도록 별도의 저장공간을 할당하여 데이터(Key)의 위치정보(Value)를 저장한다.그리고 별도의 저장공간 속에서도 원하는 정보를 찾기 쉽게 인덱스 데이터를 정렬(B Tree)한다.

 즉 인덱스에서 내가 원하는 데이터(키워드)를 먼저 찾고, 같이 저장되어있는 물리적 주소로 찾아가서 그 키워드에 대한 정보를 읽을 수 있다. 

인덱스의 활용

1) 조건 검색 Where 절의 효율성

테이블을 만들고 안에 데이터가 쌓이게 되면 데이터(record ,row)들은 내부적으로 순서가 없이 뒤죽박죽 저장된다. 

예를들어 아래의 테이블에서 레코드는 순서 없이 저장된다. (물리주소는 아래 인덱스테이블의 이해를 돕기 위해 표시했다.)

만약 여기서 이름이 조현동인 데이터를 찾고 싶다면 다음과 같은 쿼리가 필요하다. 

SELECT 이름
FROM 스터디A
WHERE 이름="조현동"

이때 데이터베이스는 WHERE절의 조건에 맞는 데이터들을 모두 찾기 위해 테이블내의 데이터를 처음부터 끝까지 읽고 조건과 맞는지 비교하는 작업을 수행한다. (== Full Table Scan) 

하지만 인덱스 테이블은 데이터들이 설정된 컬럼 값이 정렬되어 저장된다. 따라서 해당 조건에 맞는 데이터들을 보다 빠르게 찾아낼 수 있다. 

예를들어 다음과 같은 인덱스 테이블이 존재한다. (여기서는 위의 예시 테이블과 다르게 실제로 물리주소가 저장된다.)

인덱스테이블은 이름순(ㄱㄴㄷ)으로 정렬되어있고 조현동을 찾기 위해 이진탐색이든 뭐든 사용하여 기존의 WHERE 절에서 많은 시간을 차지하던 풀 테이블 스캔방식보다 빠르게 원하는 정보의 물리주소를 찾을 수 있을것이다. 

2) 정렬 ORDER BY 절의 효율성

 인덱스를 사용하면 이미 정렬되어 있으므로  ORDER BY에 의한 정렬 과정을 생략할 수 있다. 

 ORDER BY또한 부하가 큰 작업중 하나이다. 정렬과 동시에 1차적으로 메모리에서 정렬이 이루어지고 메모리보다 큰 작업이 필요하다면 디스크 I/O도 추가적으로 발생된다. 인덱스를 사용하면 이러한 전반적인 자원의 소모를 하지 않고 이미 정렬된 인덱스 테이블을 가져다 보여주면 되므로 ORDER BY 절 또한 빠르고, 간단하게 처리할 수 있다. 

3) MIN, MAX의 효율적인 처리 

 정렬되어 있지 않은 데이터에서 MIN값과 MAX값을 찾으려면 FULL TABLE SCAN으로 찾아야한다. 이미 정렬되어 있는 INDEX TABLE을 활용하면 처음 값(혹은 마지막 값)을 가져오면 된다. 

그럼 모든 데이터에 대해 인덱스를 만들어주면 빠르게 찾고 좋지 않을까?

 책의 예시를 보자. 극단적으로 생각해보면 책 한권의 내용을 한 번 더 뒤에 정렬해서 붙여야한다.   그럼 100페이지 책도 200페이지 가깝게 되고 대한민국 학생들은 승모근때매 얼굴이 커보이는 상황이 발생한다.

이러한 극단적이고 1차원적인  상황을 포함해서 왜 인덱스를 남발하면 왜 안될까??

인덱스를 남발하면 안되는 이유

 가장 큰 이유는 정렬이다. 인덱스는 정렬때매 사용하고, 정렬때매 남발하면 안된다.

 인덱스 테이블은 항상 정렬된 상태를 유지해야한다. 정렬된 테이블에 새로운 인덱스 데이터를 넣어보자. 2022년 8월 14일까지 알려진 자료구조에는 원하는 순서(위치)에 데이터를 삽입하는 경우 최소 O(logN)의 시간복잡도가 필요하다. 삽입할때만 문제가 아니다. 테이블에서 값이 변경되면, 그에 해당하는 인덱스 테이블의 값도 변경해야하고, 변경된 값을 기준으로 다시 위치를 찾아 인덱스 테이블을 정렬해야한다. 

1) DML에 취약하다. 

 일반 테이블에서 INSERT, UPDATE, DELETE 문이 수행되면 인덱스 테이블은 바빠진다. 

 예를 들어 일반 테이블에서 값을 UPDATE했다. 그럼 인덱스테이블에서 변경된 값을 찾아야하고 수정해서, 정렬해야한다.

 데이터를 저장하기 위해 흔히 *트리구조(B, B+ 트리구조)를 사용한다. 트리구조의 특성상 값이 변경 될 경우 해당위치의 노드를 삭제하고 정렬 후 새로운 값을 넣어 재정렬을 해야한다. 이런 과정을 UPDATE, DELETE문을 만날때마다 실행하면 성능(속도)이 안좋아 질 수 밖에 없다.

 이러한 문제를 조금이나마 해소하고자 인덱스는 DML문을 만나면 아래와 같이 작업을 수행한다. 

- INSERT   : 새로운 데이터에 대한 인덱스 추가.

- UPDATE  : 변경하는 인덱스를 사용하지 않음 처리(변경 후 자식 노드들에 대한 추가 정렬과정이 필요 없어짐) 이후 변경된(새로운) 데이터에대해 인덱스 추가 후 정렬.

- DELETE  : 삭제하는 인덱스를 사용하지 않음 처리(삭제 후 정렬과정 필요 없어짐) 

 이런짓을 해도 여전히 일반 테이블보다 많은 작업을 필요로한다.

또한 사용하지 않음 처리는 실제로 삭제되는것이 아니기 때문에 인덱스테이블이 과도하게 커지는 문제가 발생할 수 있다. 

따라서 DML이 빈번한 테이블보다는 검색을 위주로 하는 테이블에 INDEX 생성하기를 추천한다. 

2) 인덱스 스캔이 무조건 더 빠르고 좋은것은 아니다.

 인덱스로 값을 가져오는게 개사기인거처럼 말해놨지만 사실 항상 FullTableScan보다 좋은건 아니다.

대량의 데이터(넓은 범위의 데이터)를 읽어야 할 경우, 데이터의 형식이 적은경우 인덱스 스캔을 다시 한 번 생각해봐야한다.

 (아래는 이해가 안되가지고 여러블로그 참조해서 억지로 이해한 내 판단이고 반박시 반박이 맞을 확률 큼)

 넓은 범위의 데이터 액세스작업이 필요하다면 Full Table Scan이 효율적이다. 인덱스 스캔의 경우 값을 한 번에 읽어들이는 양(버퍼)이 적지만 Full Table Scan은 한 번에 읽어들이는 양이 많다. 따라서 인덱스 스캔은 빠르게 찾더라도 I/O작업이 여러번 발생하는 반면 FullTableScan은 느리게 찾지만 I/O작업이 적게 발생한다. ( 두개의 시간차이를 고려해서 DBMS는 넓은 범위를 읽고자 할 때 INDEX가 존재하더라도 Full Table Scan 한다. ) 

 넓은 범위라 했지만 사실 그렇게 넓은 범위도 아니다. 데이터의 양이 충분히 많을때 전체 데이터의 10~15% 이상의 데이터를 처리해야한다면, Full Table Scan이 효율적이다. 

3) 속도 향상을 위해 인덱스를 많이 만드는것은 좋지 않다. 

 인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장공간이 추가로 필요하다. 무턱대고 인덱스를 많이 만들면 안되고, 장단점을 비교하여 장점으로 작용할수 있는 작업(좁은 범위 읽기)을 더 많이 할 경우, 인덱스를 사용하고 단점으로 작용할 수 있는 작업을 많이 할 경우 (넓은 범위 읽기, 수정, 삭제, 삽입) 인덱스를 포기하는 것이 적절하다.

어떤 컬럼을 인덱스로 만들어야 할까?? 

1. 조건절에 자주 등장하는 컬럼

2. 항상 = 으로 비교되는 컬럼 

3. 중복되는 데이터가 최소한인 컬럼

4. ORDER BY 절로 자주 사용되는 컬럼 

5. JOIN조건으로 자주 사용되는 컬럼 

위의 조건들을 살펴보면 PK가 최선이자 주로 선택되는 인덱스이다. 

만약 중복이 가능한 컬럼으로 인덱스를 생성하여 모든 데이터가 중복이라면, 일반 테이블과 검색속도가 같은 용량만 차지하는 똥덩이 악효과를 보여줄 것이다. 

인덱스 자료구조 

Q2-1 ) DB (INDEX)에서 사용하는 대표적인 자료구조가 무엇이 있을까요? 
A2-1) 이진트리에서 발전된 B (B+)Tree가 주로 사용됩니다.  
실제 데이터베이스는 B+트리가 주로 사용된다.

Q2-2 ) B트리가 뭔가요??
A2-2) 이진트리 중 leaf노드의 레벨차이가 최대 1인 균형이진트리, 균형이진탐색트리와 유사합니다. 균형이진탐색트리와는 다르게 하나의 노드에 여러개의 값을 가질 수 있으며, 여러개의 자식노드를 가질 수 있는 자료구조 입니다. 이때 자식노드로 가질 수 있는 최대 개수가 M이라면 M차 B Tree라고 불립니다. 

Q2-3) B, B+트리의 차이점은 뭔가요??
A2-3)
B Tree는 모든 노드에 데이터를 저장하는 반면,
B+ Tree는 B트리에서 발전된 형태로 leaf노드(==Data 노드)에만 데이터를 저장하고, leaf노드가 아닌 노드(==Index, Inner 노드)에는 자식노드를 가리키는 포인터값만 가지고 있으며, leaf노드끼리는 linked list 구조로 연결되어있습니다. 

Q2-4) 설명해주신 B+트리의 구조는 B 트리와 비교해서 어떤 이점을 갖게 되나요?
A2-4) B+ Tree는 전체 데이터를 순회할때 leaf 노드에 접근하여 linked list구조로 연결되어 있는 다른 leaf노드에 접근하면 되므로 전체 노드를 순회해야하는 B Tree보다 효율적으로 데이터를 순회할 수 있습니다. 
A2-4++) B+ Tree에서 leaf노드가 아닌 노드(= 비단말 노드=Index, Inner 노드)는 데이터가 없어서 B Tree보다 Inner노드에 대해 차지하는 용량이 적으므로, 하나의 디스크 블록에 더 많은 Inner노드를 담을 수 있습니다. 이러한 이점은 Key를 탐색하기 위해 비교적 적은 디스크 블록만을 읽어도 됩니다. 따라서 디스크의 접근수를 줄임으로 속도를 높여줄 수 있고 디스크의 저장공간을 보다 효율적으로 사용할 수 있습니다. 

+a)
https://www.cs.usfca.edu/~galles/visualization/BTree.html 

균형이진트리

• 균형이진트리 - 모든 leaf노드의 레벨차이가 최대1인 이진트리

균형이진트리는 보통 하나의 노드가 하나의 값을 가지고, 최대 두개의 자식노드를 가질 수 있다. 

B Tree는 균형이진탐색트리에서 확장된 개념으로 간단하게 알아두면 이해하기 쉽다. 이진탐색트리의 삽입삭제수정 과정은 따로 검색해보자. 

B Tree

 균형이진트리와 다른점은 하나의 노드가 여러개의 값을 가질 수 있다. 여기서 차수라는 개념이 등장한다.  예를들어 하나의 노드가 최대 M-1개의 값을 가질 수 있다면, 최대 M개의 자식노드를 가질 수 있는데 이 B Tree는 M차 B Tree이다. 

M차 B Tree의 특징

• 노드는 최대 M개부터 최소 M/2개의 자식노드를 가질 수 있다.
• 노드에는 최대 M-1개부터 최소 int((M-1)/2) 개의 키(데이터)가 포함될 수 있다.
• 노드의 키가 x개라면 자식노드의 수는 x+1개이다. 

B Tree 예시

위의 그림은 차수가 3(M=3)인 B Tree이다. 하나의 노드에서 파란색 부분은 Key(데이터)이고, 빨간색 부분은 자식노드를 가리키는 포인터이다. 

데이터들은 노드안에서 정렬된 상태를 유지하고, 일반 이진검색트리와 같이 데이터의 왼쪽에는 데이터보다 작은 값, 오른쪽에는 큰 값을 저장한다. 

B+ Tree

B 트리는 하나의 값을 찾을때 좋은 성능을 보여준다. 하지만 DB에서는 모든 데이터(일정 범위)를 순회해야할 경우가 많다. 

B 트리(위의 예시)에서 모든 데이터를 순서대로 순회하려면,

• 7->4->2 -> 4 -> 6 -> 4 -> 7 -> 9-> 8 -> 9 -> 10 -> 11 -> 12 -> 14 -> 11 -> 15..

위와 같이 여러번의 노드간 이동이 필요하다. B+ Tree는 B Tree의 데이터 순회, 범위 검색 등의 단점을 보완하기 위해 탄생했다. 

B+ Tree 예시

leaf노드가 아닌 노드 (Inner, Index, 비단말 노드) 들은 data를 가지고 있지 않으며, 자식노드를 가리키는 포인터 값만 가지고 있다. 

leaf노드(Data, 단말 노드)는 data를 가지고 있으며 각 leaf노드들은 linked list로 연결되어있다. 

따라서 B+트리에서 전체 데이터를 순회하고 싶다면 

7 -> 4 -> 2 -> 4 -> 7 -> 9 -> 11 -> 14 -> 15 -> 17 -> 20

위의 과정이면 충분하다. 불필요한 노드간의 이동을 줄였고, 비단말노드들의 필요한 용량을 줄여 데이터를 효율적으로 저장할 수 있게 됐다. 

하지만 key=7의 값은 루트노드에 있음에도 불구하고 data를 얻으려면 leaf노드까지 내려가야한다는 단점이 있다.