퀴즈 7회차

 List

- 배열과 연결 리스트는 새로운 원소를 마지막 위치에 추가하는 연산에 대해서는 공통적으로 상수시간 =O(1)으로 수행한다.

- 배열은 임의적으로 접근이 가능하며 시간복잡도는 O(1)이다.

- ArrayList는 메모리 공간을 연속적으로 사용하지만 , LinkedList는 메모리 공간을 랜덤하게 사용한다.

- 연 결리스트는 포인터(혹은 연속자)가 주어진 상황에서는 전후 원소들과의 연결관계만 조정해주면 되므로 상수시간=O(1)이 소모된다.

 

 

-스택과 큐는 배열, 연결리스트로 구현할 수 있다.

 

 해시 테이블

- 원소의 해시값을 계산해 저장할 위치를 구한다.

- 이상적으로 모든 CRUD연산에 대해 O(1)의 시간 복잡도를 가진다.

- 해시충돌을 극복하여 원소를 저장하는 방법에는 대표적으로 separate chaining과 open addressing 기법이 있다.

- 저장할 공간이 부족한 경우 저장 성능이 급격히 떨어지므로 빈 저장공간을 약 25% 정도 확보해놓는 것이 좋다.

 

 정렬 알고리즘

- 퀵소트는 평균 시간복잡도는 O(logN)이지만 이미 정렬 또는 역정렬된 입력 같은 최악의 경우 시간복잡도는 O(N^2)이다.

- 메모리 여유가 없다면 병합정렬보다 퀵소트가 더 나은 선택이다.

- 동일한 원소의 자리가 바뀌지 않기를 원한다면 퀵소트보다 병합정렬이 더 나은 선택이다.

 

시간복잡도는 알고리즘의 소요시간을 입력 크기에 대하여 추상화한 것으로서, 소요시간을 추정하는 데 도움이 되지만, 현실과 이상은 다르다. 시간복잡도가 뛰어난 알고리즘의 경우 구현이 복잡하므로 생략되는 계수가 크다. 따라서 입력이 충분히 작은 경우에는 시간복잡도가 느린 알고리즘이 시간복잡도가 빠른 알고리즘보다 더 빠를 수 있다. 삽입정렬도 마찬가지다.

 

 트리

- 트리는 비선형적이며 계층적인 자료구조다.

- 그래프에 조건을 추가하면 트리가 될 수 있다.

- 이진트리는 자식 노드가 최대 2개인 노드들로 구성된 트리다.

 

 트랜잭션

- 트랜잭션 스케줄이 복구 가능하려면 모든 트랜잭션에서 데이터를 조회할 때 commit된 데이터만 읽어야 한다. -  원자성을 보장하기 위해서는 undo log를 역순으로 실행하여 완료되지 않은 트랜잭션을 실행 전 상태로 초기화(롤백)하고, 지속성을 보장하기 위해서는 redo log를 순서대로 실행하여 완료된 트랜잭션들이 적용되게 한다(리플레이). - 데드락이 감지되면 연관 트랜잭션을 롤백한다.

- MVCC를 활용하는 현대적 DMBS들은 읽기 락(shared lock)을 사용하지 않아서 성능상 이점이 있다.

 

 디스크 기반 DBMS의 스토리지와 인덱스- 디스크 액세스 속도가 메인메모리 엑세스 속도보다 매우 느리므로, DBMS는 최대한 디스크 액세스를 줄이는 방향으로 설계된다. - 인덱스를 사용하면 DML 요청시 디스크 스페이스 이외에 인덱스 스페이스에서 인덱스를 관리하기 위한 별도의 작업이 이루어지므로, 일반적으로 읽기를 제외한 나머지 DML의 성능이 저하된다. -  tree 인덱스는 범위 탐색이나 정렬에 활용될 수 있으나 연산이 복잡하다. - hash 인덱스는 인덱스 관리 연산이 비교적 단순하지만 단일 탐색만 가능하다.

 

  DBMS의 쿼리 프로세싱- Optimizer는 규칙 또는 비용을 기준으로 삼아 여러 실행 계획들을 생성하고 각 계획들의 실제 비용을 추산한 값을 비교 평가하여 SQL 명령을 내부적으로 어떻게 실행할지 결정한다. -  Optimizer가 생성할 수 있는 모든 실행계획을 만들어서 비교하는 것은 사실상 불가능하므로 다양한 기법을 통해 생성될 실행계획을 제한한다.- 옵티마이저의 조인 전략은 여러 가지가 있으나, 쿼리에 ORDER BY가 포함되면 해시 조인보다 소트 머지 조인이 비용이 적은 실행 계획일 가능성이 높다. - 인덱스 접근이 발생하긴 하지만, 인덱스를 통해 실제 데이터에 바로 접근하므로 seek time/rotational time 등이 줄어들어서 일반적으로 조회시간이 줄어든다.

 

 분산 데이터 

- 분산 데이터베이스는 데이터베이스가 서로 다른 물리적인 공간에 분산되어 있는 시스템을 말한다. - 분산 데이터베이스는 데이터가 분산되어 있으므로 부분 시스템의 실패에 대한 높은 대응력을 가진다.

 

 NOSQL

- NoSQL은 확장성에 초점을 맞춰 비교적 유연한 데이터모델을 가지며, 일반적으로 (대체 연산은 제공하더라도) 기본적인 JOIN 연산을 제공하지 않기 때문에 JOIN 연산이 필요한 복잡한 연관관계를 갖는 시스템에는 적합하지 않다.

- NoSQL은 데이터 정합성을 일부 포기하는 대신, 데이터의 가용성과 확장성, 접근 시간에 초점을 맞춘다.