[데이터베이스] 기초 개념 정리

파일시스템

데이터베이스가 등장하기 전에는 파일 시스템으로 데이터를 관리했음

• 파일 시스템의 한계
  • 데이터 redundancy, inconsistency
    • multiple file format, duplication of information in different files
    • 여러 사용자가 concurrrent access하면 consistency가 지켜지기 어려움
  • 데이터 접근의 어려움: 데이터 접근하려고 새 프로그램을 작성해야 함
  • 연동의 어려움: 프로그램 코드에 제약 조건을 추가해야 하고, 새 제약 조건을 추가하거나 변경하는 것이 어려움
  • 업데이트 시 원자성(atomicity)가 안 지켜짐
  • 권한 관리: 파일 권한 관리는 되나, 데이터 레벨 권한 관리는 안 됨

---

Database Language

• Data Definition Language (DDL)
  • DB 스키마 변경에 사용
    • create table
    • drop column
• Data Manipulation Language (DML)
  • DB의 data를 변경할 때 사용

SQL

• Join
  • Inner join: 디폴트로 설정된 join
  • Outer join: 정보 손실 없이 join

Transaction

• 논리적인 작업 셋을 완벽하게 처리하거나 또는 처리하지 못할 경우에 원 상태로 복구해서 작업의 일부만 적용되는 현상이 발생하지 않게 만들어 줌
• 데이터의 정합성을 보장하기 위한 기능
• 특징: ACID
  • atomicity: all or nothing
  • consistency: 데이터의 일관성을 보장
  • isolation: 각 transaction 서로 독립적이어야 함
  • durability: 트랜잭션이 정상적으로 종료되면 DB에 작업 결과가 영구적으로 남아야 함

Lock

• 동시성을 제어
• 여러 커넥션에서 동시에 동일 자원을 요청할 경우 순서대로 한 시점에는 한 커넥션만 변경할 수 있게 함

---

Relational Database Design

관계형 DB는 잘못 설계하면 정보가 반복되거나 정보가 손실될 수 있음... 특히 정보의 중복은 insertion, deletion, update 시에 정보의 inconsistency를 초래할 수 있음!

따라서 스키마를 쪼개서 각 정보가 한번만 표현되도록 바꿔야 함 => 정규화!

정규화

• 단점
  • 릴레이션의 분해로 join 연산이 많아짐

Storage Hierarchy

cache - main memory - flash memory - magnetic disk - optical disk - magnetic tape 순

• primary storage
  • 가장 빠름
  • volatile
  • cache, main memory
• secondary storage
  • 휘발되지 않음 (non-volatile), 비교적 빠름
  • on-line storage: operation이 돌아갈 때 사용
  • flash memory, magnetic disk(하드 디스크)
    • magnetic disk: 원판을 돌려서 읽어야 할 데이터가 저장된 위치로 arm을 옮겨야 함. 따라서 arm을 움직여서 위치로 옮기는 단계를 줄여야 빨리 읽을 수 있음
      • 메인 메모리와 디스크는 block 단위로 date를 주고 받음
      • file organization: block access 시간을 줄이기 위해 block들을 access될 순서로 정렬
        • 예) 관련된 정보를 인접한 block에 저장
      • log disk를 분리: a disk devoted to writing a sequential log of block updates
        • sequential access가 성능이 가장 좋으므로
• tertiary storage
  • non-volatile, 느림
  • 백업용 (off-line storage)
  • magnetic tape, optical storage

RAID (Redundant Arrays of Independent Disks)

• n개의 디스크를 엮어 하나의 disk system으로 사용
• reliability by redundancy
  • disk failure에 대비해 데이터의 여러 복사본을 디스크에 나누어 둠
• performance by parallelism
  • disk에 데이터를 나눠 놓아 transfer rate를 높임 
  • bit-level striping
    • byte의 bit의 multiple disk에 나눔 (8비트가 1바이트)
  • block-level striping
    • block들을 여러 디스크에 나눔 (디스크 대수만큼 block number를 모듈러 연산해서 블록을 저장할 위치 결정)

---

Index

데이터 access time을 줄이기 위해 등장

• primary index (=clustering index)
  • primary key 값이 비슷한 레코드들끼지 묶어서 저장
  • primary key 값에 의해 레코드의 저장 위치가 결정됨 (primary key 값이 변경되면 그 레코드의 물리적인 저장 위치 또한 변경되어야 함)
  • 테이블 당 1개만 생성 가능
  • 만약 primary index가 memory에 들어가지 않으면 data 접근 비용이 비싸짐 (오래 걸림) => multilevel index!
    • Multilevel index: primary index 파일이 클 경우 큰 파일을 disk에 두고, 그에 대한 sparse index를 만들어 메인 메모리에 저장
      • 기본적으로 tree의 구조여서 worst-case의 경우에 access time이 O(n)이 걸림
• secondary index (=non-clustering index)
  • an index whose search key specifies an order different from the sequential order of the file

인덱스 생성 시에 insert, delete, update 쿼리문을 실행할 때 별도의 과정이 추가적으로 발생함

따라서 무조건 모든 컬럼에 index를 두는 것보다 디스크 I/O가 최대한 덜 발생하는 컬럼을 뽑아 인덱스로 만드는 것이 좋음

Index 자료 구조

B-tree

• 특정 key 값이 하나의 노드에서만 존재할 수 있음

B-tree와 대비되는 B+-tree의 특징

• 특정 key 값이 internal 노드와 leaf 노드에 공존할 수 있음
• internal node들은 데이터의 빠른 접근을 위한 인덱스 역할만 함
• leaf node는 linked list 형태로 서로 연결되어 있음
• 순차적 접근이 가능

B+-tree

• balanced index tree 
  • 일종의 balanced tree (avl tree, red-black tree, B-tree)
    • 삽입과 삭제 시에 필요하면 스스로 균형을 유지함 => 항상 O(logN)의 검색 성능
• 조건
  • 하나의 노드에 여러 data가 들어감
    • 최대 n개의 자료가 한 노드에 들어가면 n차 B-Tree
  • 각 노드의 data는 정렬된 상태여야 함
  • root에서 leaf까지의 거리가 모두 같음 (leaf node가 모두 같은 레벨)
  • root, internal node, leaf node로 구성됨
    • internal node: at least half full
    • leaf node: file 레코드에 대한 dense index
• 장점
  • 삽입, 삭제 시에 스스로 reorganize하면서 balanced 상태(at least half full)를 유지
    • 검색이 O(logN)
  • range query가 가능
• 단점
  • 삽입, 삭제 시에 오버헤드가 있음
  • space 오버헤드

Hash 

• 컬럼의 값을 해시 값을 계산해서 인덱싱하는 알고리즘
• 빠른 검색을 지원
• uniform한 분포로 random(키 값의 distance가 h(k1), h(k2)의 distance와 무관해야)하게 분배하는 hash function이 좋음
• hash index: search key, 실제 record의 포인터를 따로 index로 관리. 
• 종류
  • static hashing
  • dynamic hashing:
    • hash function이 dynaic하게 변할 수 있음
      • database size가 변할 때 좋음
    • extendable hashing: 
      • hash function이 b-bit integer를 계산해 주면, 필요한 bucket 수에 따라 prefix만 사용
• 장점
  • minimal space overhead
• 단점: 
  • extra level of indirection
    • hash -> table -> data
  • overflow나면 굉장히 느려짐 (단 average의 경우에는 빠름)
  • range query를 지원하지 않음

---

NoSQL

대량의 분산된 데이터를 저장, 조회하는 데 특화됨

스키마 없이 사용 가능하거나 느슨한 스키마를 제공하는 저장소

 

---

참고 자료

github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Database