설탕빵의 설탕공방과거에 질문을 하나 받은 적 있다.
"데이터베이스 라는 시스템을 만들기 위해 자료구조를 사용한다면 어떤 구조를 사용 할 것인가?"
당시에는 지식이 부족해서 제대로 된 답을 하지 못했다.
요즘 DB 아키텍처 적으로 조금 고민 중이라 한번 DB에 자료 구조에 대해서 알아보고자 한다.
RDBMS왜 나왔는가
일단 기술이란 과거에 뭔가 문제나 불편함이 있기 때문에 나왔다.
RDBMS이전에 사람들은 데이터를 그냥 파일 시스템에서 쓰고 읽기를 했었다.
파일 시스템을 기반으로 하니깐,
데이터 쓰는 프로그램이 파일이라는 물리적(컴퓨터 시스템 기준) 저장 구조에 맞물려 있으니 데이터 종속 문제가 있었다.
또한 데이터에 대한 관계같은게 확립이 안되어있는 상태다 보니,
데이터에 대한 중복 관리가 어려웠다.
그럼 RDBMS는 어떻게 처리하는가?
일단 우리가 물리적인 파일 자체를 몰라도 데이터 접근 및 처리가 가능하다.
데이터 또한 2차원 테이블 형태로 표현되어있기에 처리하기 편하다.
테이블 간의 관계에 대한 또한 기본키, 외래키를 통해 논리적인 관계를 구축하고 데이터 조인을 해서 조회하기 편하다.
근데 결국 파일 시스템 쓰는건 똑같지 않는가
사실 과거에 물리적 데이터 파일에 저장한다랑
지금 물리적 데이터 저장하고 접근하는 논리적 구조(테이블)을 분리 시킨거면 결국 둘 다 파일 시스템 쓰는 건 같은 거 아닌가 싶을 수 있다.
다만 데이터에 어떻게 접근하느냐에 차이가 존재한다.
데이터베이스에서 데이터를 접근한다는 것은 결국 인덱스를 통한 접근이다.
내가 찾고자 하는 데이터가 어디에 위치하는지에 대한 색인이 기본인 것이다.
색인 구조를 설명하기위해
이진트리 자료구조를 먼저 설명하겠다.
이진트리는 하나의 요소가 2개의 자식 노드를 가진다.
이진트리 방식을 사용하면 전체에 데이터를 확인하는 거에서
왼쪽이냐, 오른쪽이냐 2개의 선택지로 분기된다.
즉 연산이 O(log n) 형태가 되는 것이다.
다만 이런 방식은 노드의 깊이가 너무 높아진다.
노드를 하나 읽을 때마다 디스크 I/O가 1번 발생한다고 하면
노드가 깊어질수록 I/O 횟수가 늘어나는 것이다.
이 문제에 대해서 RDBMS는 색인에 B+Tree 방식을 사용한다.
B+Tree
일단 이전에 B-Tree 구조가 별도로 있었는데
B Tree 계열은 이진트리에 depth 문제를 해결하기 위해
하나의 노드가 가질 수 있는 자식 노드의 개수를 늘려서 depth와 노드 탐색 사이에 균형을 추구하는 방식이다.
B-Tree는 여기서 각 노드가 Key/Value 구조로 데이터를 가지도록 한다.
데이터를 찾을 때 가까운 곳에 찾는 데이터가 있다면 리프 노드까지 내려가지 않아도 검색이 가능하도록 하는 것이다.
다만 단점으로는 해당 데이터가 순차적으로 정렬된 것은 아니기에,
10~100까지 찾는 Range 검색에서는 내부적으로 오르락 내리락하면서 비효율적인 탐색 과정이 발생한다.
이 문제를 해결하는 것이 바로 B+Tree 구조로
데이터 저장 노드와 안내 노드를 분리한다.
내부 노드는 Key와 포인터만 저장해서 안내 역할을 수행한다.
모든 데이터는 리프 노드만 가지게 되며, 서로간 Linked List 방식으로 연결되어있다.
즉 10번 데이터에서 다음 리프 노드의 연결 리스트를 따라서 쭉 진행하면 된다는 것이다.
단점
B+Tree는 데이터를 정렬된 상태로 유지해야 한다.
만약에 Insert 등의 이벤트로 중간 데이터에 변화가 생기면,
해당 사항을 반영하기 위해 정렬과 저장 작업이 진행된다는 것이다.
이 과정에서 디스크 헤드가 이리저리 움직이는 Random I/O가 발생한다.
이러한 구조 때문에 RDBMS는 읽기에는 강하지만, 쓰기 부하가 매우 클 때 병목 현상이 생긴다.
마무리
Page 내용 없고
인덱스를 PK를 기준으로 하고 Secondary Index인 경우는 내용이 조금 안 맞을 수 있는데,
그냥 편하게 쉽게 쓰려고 했다.
어차피 Clustered 구분 하실 줄 아시면 이 글 보실 필요 없을 테니 가볍게 넘어가주시길 바란다.