DB

이진 탐색 트리 (BST) - 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가짐 - 자녀 노드는 최대 두 개까지 이런 이진 탐색 트리의 특징을 사용하면서도 자녀 노드의 최대 개수를 늘리기 위해서 B tree를 사용함. B tree - B tree는 BST를 일반화한 tree - 자녀 노드의 최대 개수를 늘리기 위해 부모 노드에 key를 하나 이상 저장함 - 부모 노드의 key들을 오름차순으로 정렬함 - 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정됨 이런 방식을 사용하면 자녀 노드의 최대 개수를 입맛에 맞게 결정해서 쓸 수 있음. 최대 몇 개의 자녀 노드를 가질 것인지가 B tree를 사용할 때 중요한 파..

DB에서 index를 쓰는 이유 - 조건을 만족하는 튜플(들)을 빠르게 조회하기 위해서 - 빠르게 정렬(order by)하거나 그룹핑(group by)하기 위해서 대부분 B-tree 기반으로 동작하는 index가 많음. 시간복잡도는 O(logn) 인덱스 거는 방법 name 이라는 conttribute는 동명이인이 있을 수 있기 때문에 그냥 INDEX 명령어로 처리하는 것이고, team_id와 backnumber는 중복값이 있을 수 없기 때문에 (같은 팀에 같은 등번호 X) UNIQUE INDEX 명령어로 처리함. 예시의 UNIQUE INDEX처럼, 두 개 이상의 attribute로 구성된 인덱스를 multicolumn index 또는 composite index 라고 함. primary key에는 ind..

DB 정규화 (normalization) - 데이터 중복과 insertion, update, deletion anomaly를 최소화하기 위해 일련의 normal forms(NF)에 따라 relational DB를 구성하는 과정 Normal forms - 정규화 되기 위해 준수해야 하는 몇 가지 rule들이 있는데 이 각각의 rule을 normal form(NF)라고 부름 DB 정규화 과정 - 처음부터 순차적으로 진행하며 normal form을 만족하지 못하면 만족하도록 테이블 구조를 조정함 - 앞 단계를 만족해야 다음 단계로 진행할 수 있음 e.g.) EMPLOYEE_ACCOUNT bank_name account_num account_id class ratio empl_id empl_name card_i..

Functional dependency - 한 테이블에 있는 두 개의 attribute(s) 집합(set) 사이의 제약(a constraint) X 값에 따라 Y 값이 유일하게(uniquely) 결정될 때 'X가 Y를 함수적으로 결정한다(functionally determine)' 'Y가 X에 함수적으로 의존한다(functionally dependent)' 라고 말할 수 있고, 두 집합 사이의 이러한 제약 관계를 functional dependency(FD)라고 부름. (X -> Y) 화살표의 왼쪽 부분은 left-hand side, 오른쪽 부분은 right-hand side 라고 부름. e.g.) EMPLOYEE empl_id empl_name birth_date position salary dept_..

LOCK - based concurrency control - 같은 데이터에 대해서 서로 다른 트랜잭션이 read, read 하는 경우에는 허용하지만, 그 외의 경우에는 허용하지 않아서 한 쪽이 실행되면 다른 한 쪽은 blcok이 돼서 기다려야 하기 때문에 동시에 처리할 수 있는 처리량이 줄어들어서 퍼포먼스에 안 좋은 영향이 있음. LOCK - based concurrency control 의 문제를 해결하기 위해서 MVCC가 등장하게 됨. MVCC (multiversion concurrency control) - 같은 데이터에 대해서 서로 다른 트랜잭션이 write, write 하는 경우에는 한 쪽이 block 되지만, 그 외의 경우에는 block이 되지 않고 동시에 처리가 가능하기 때문에 동시에 처리..