데이터베이스 & 자료구조 Q&A

1. WHERE과 HAVING의 차이에 대해 설명해주세요.

• where은 기본적인 조건절로서 우선적으로 모든 필드를 조건에 둘 수 있습니다. 하지만 having은 group by 된 이후 특정한 필드로 그룹화 되어진 새로운 테이블에 조건을 줄 수 있습니다.
• 즉, 전체 테이블 자체에서 쿼리를 수행하고 싶다면 where를, 전체 테이블을 그룹화 한 뒤, 그 해당 그룹에서 어떠한 조건을 걸어 가져오고 싶다면 having을 사용합니다.
  https://wansook0316.github.io/cs/database/2020/04/25/where-having-%EC%B0%A8%EC%9D%B4.html

2. 데이터베이스 트리거(Database Trigger)에 대해 설명해주세요.

• 테이블에 대한 이벤트에 반응해 자동으로 실행 되는 작업을 의미합니다. INSERT 나 UPDATE 또는 DELETE 작업이 발생되면 자동으로 실행되는 코드입니다.
• 수작업으로 하게 된다면? 데이터의 신뢰성이 떨어지고, 데이터의 구조도 망가지게 되는 경우가 생길 수 있습니다. 이러한 실수를 대비하기 위해 자동으로 삭제 작업이 일어날 경우 삭제 되기 전에 미리 다른 곳에 삭제될 데이터를 자동으로 저장해 주는 기능 이 대표적인 트리거(TRIGGER)의 사용 용도입니다.
  https://hanhyx.tistory.com/20

3. DB의 무결성을 유지하려는 이유가 무엇인가요?

• 데이터의 신뢰성과 일관성을 보장하고, 데이터베이스 시스템의 안정성을 확보하기 위함입니다. 무결성이 유지되어야 DB에 저장된 값과 현실세계의 실제 값이 일치하는 지를 보장할 수 있습니다.

4. 데이터베이스 레플리케이션(Replication)이 무엇인지 설명해주세요. 장단점이 무엇인가요?

• 하나의 데이터베이스 서버(마스터)에서 발생하는 데이터 변경 사항을 다른 하나 이상의 데이터베이스 서버(슬레이브)로 복제하는 프로세스를 의미합니다. 여러 개의 DB를 수직적인 구조(Master - Slave)로 구축하는 방식을 말합니다. Master Node는 쓰기 작업만을 처리, Slave Node는 읽기 작업만을 처리하며, 비동기 방식으로 노드들 간의 데이터 동기화한다는 특징이 있습니다.
• 장점: DB 요청의 대부분이 Read이기 때문에 성능 상 이점이 있습니다. 비동기 방식으로 운영되어 지연 시간이 거의 없습니다. 데이터의 가용성, 복원력, 성능, 로드 분산 등을 향상시킬 수 있습니다.
• 단점: 노드들 간의 데이터 동기화가 보장되지 않아 일관성있는 데이터를 얻지 못할 수 있습니다. Master 노드가 다운되면 복구 및 대처가 까다롭습니다.
  https://bryceyangs.github.io/study/2021/06/01/Database-Sharding-&-Replication-&-Clustering/

5. 커넥션풀이란 무엇인가요?

• 커넥션 풀은 데이터베이스와 연결된 커넥션을 미리 만들어 놓고 이를 pool로 관리하는 것이다. 즉, 필요할 때마다 커넥션 풀의 커넥션을 이용하고 반환하는 기법이다. 이처럼 미리 만들어 놓은 커넥션을 이용하면 Connection에 필요한 비용을 줄일 수 있다. 따라서 DB에 빠르게 접속할 수 있다.
• 커넥션 풀을 사용함으로써 데이터베이스와의 연결 관리에 대한 부담을 줄일 수 있으며, 연결 생성 및 해제 작업으로 인한 오버헤드를 최소화할 수 있습니다. 이로써 애플리케이션의 성능을 향상시키고 데이터베이스 서버의 부하를 줄일 수 있습니다. 또한 커넥션 풀을 사용하면 커넥션 수를 제한할 수 있어서 과도한 접속으로 인한 서버 자원 고갈을 방지할 수 있으며 DB 접속 모듈을 공통화해 DB 서버의 환경이 바뀔 경우 유지보수를 쉽게 할 수 있다.

++ 커넥션 풀의 크기는 어느 정도인 게 좋을까?
커넥션 풀이 크면 클수록 좋을까? 언뜻 생각해보면 커넥션을 많이 가지고 있을수록 유리할 것 같긴 하다.
하지만, Connection을 사용하는 주체인 Thread의 개수보다 커넥션 풀의 크기가 크다면 사용되지 않고 남는 커넥션이 생겨 메모리의 낭비가 발생하게 된다.
MySQL의 공식레퍼런스에서는 600여 명의 유저를 대응하는데 15~20개의 커넥션 풀만으로도 충분하다고 언급하고 있다. MySQL은 최대 연결 수를 무제한으로 설정한 뒤 부하 테스트를 진행하면서 최적화된 값을 찾는 것을 추천한다.
우아한 형제들 테크 블로그에서는 다음과 같은 공식을 추천하고 있다.
https://code-lab1.tistory.com/209

6. 인덱스를 사용하면 좋은 경우와 피해야 하는 경우에 대해 설명해주세요.

• RDBMS에서 검색 연산의 속도를 높이기 위한 방법으로, 항상 정렬된 상태를 유지하므로 탐색이 빠릅니다. 데이터 삽입/삭제/수정 시에는 추가적인 작업이 필요하므로 실행 속도가 느려집니다. 저장 성능을 희생하고 데이터 읽기 속도를 높이는 기능입니다.
• 인덱스 자료구조: B+- Tree(일반적으로 사용됨), Hash(해시 값을 계산해 검색하므로 빠르나 부분 검색을 할 수 없음)
• 인덱스를 사용하면 좋은 경우: where 절에서 자주 사용되는 Column, 외래키에 사용되는 Column, Join에 자주 사용되는 Column
• 인덱스를 피해야 하는 경우: 데이터의 중복도가 높은 Column, 삽입, 삭제, 수정 연산이 자주 일어나는 Column
  https://github.com/4z7l/tech_interview.zip/blob/main/%EC%A7%81%EB%AC%B4/Database.md

7. 낙관적 락보다 비관적 락을 사용하는 것이 좋은 상황의 예시를 들어주세요.

• 락(Lock)을 이해하기 전에 트랜잭션 격리 수준을 먼저 알아야한다. 트랜잭션 격리수준(isolation level)이란 동시에 여러 트랜잭션을 처리할 때, 트랜잭션이 얼마나 서로 고립되어 있는지를 의미한다. 즉, 해당 트랜잭션이 다른 트랜잭션에서 변경한 데이터를 볼 수 있는 기준을 결정하는 것이다. READ UNCOMMITTED/READ COMMITTED/REPETABLE READ/SERIALIZABLE. 트랜잭션 격리 수준이 높아질수록 자원을 많이 사용하고 성능이 떨어진다. 일반적으로는 READ COMMITTED나 REPEATABLE READ 중 하나를 사용한다. JPA를 사용하면 READ COMMITTED 이상의 격리 수준이 필요할 때 비관적 락, 낙관적 락을 선택해야 한다.
• 비관적 락(Pessimistic Lock): 트랜잭션이 충돌한다고 가정하고 락을 건다. DBMS의 락 기능을 사용한다. (ex. SELECT FOR UPDATE) 데이터 수정 시 즉시 트랜잭션 충돌여부를 확인할 수 있다.
• 낙관적 락(Optimistic Lock): 트랜잭션이 충돌하지 않는다고 가정한다. 자원에 락을 걸어서 선점하지말고 커밋할 때 동시성 문제가 발생하면 그때 처리 하자는 방법론입니다. JPA에서는 자체적으로 제공하는 버전 관리 기능을 사용한다. (hashcode나 timestamp를 이용할 수도 있다.) 트랜잭션을 커밋하기 전까지는 충돌 여부를 확인할 수 없다.
• 비관적 락은 조회한 레코드 자체에 락을 걸기 때문에 성능이 저하될 수 있다. 성능상 이슈가 발견된다면 낙관적 락을 고려해야 한다. 낙관적 락은 일반적으로 처리 요청을 받은 순간부터 처리가 종료될 때까지 레코드를 잠그는 비관적 락보다 성능이 좋다.
• 데이터 성향에따라, 비관적 락이 좋은 경우도 있는데 이런 경우이다. 재고가 1개인 상품이 있다. 100만 사용자가 동시적으로 주문을 요청한다. 비관적 락의 경우 1명의 사용자 말고는 대기를 하다가 미리 트랜잭션 충돌 여부를 파악하게 된다. 즉, 재고가 없음을 미리 알고 복잡한 처리를 하지 않아도 된다. 낙관적 락의 경우 동시 요청을 보낸 사용자가 처리를 순차적으로 하다가 Commit을 하는 시점에 비로소 재고가 없음을 파악하게 된다. 그리고 처리한 만큼 롤백도 해야하기 때문에, 자원 소모도 크게 발생하게 된다.
  https://jaehoney.tistory.com/159

8. 최악의 복잡도는 나쁘지만 실제로는 자주 사용되는 알고리즘에는 무엇이 있나요?

• 퀵소트의 시간 복잡도는 O(n^2)이지만, 거의 정렬된 데이터의 경우에는 O(n)에 가까운 시간복잡도를 보여 다른 정렬알고리즘 보다 나은 빠른 성능을 보입니다. 그래서 python, java와 같은 언어의 내장정렬 함수에서 사용됩니다.
• 해쉬테이블의 경우 충돌이 발생했을 경우에 O(n)의 시간복잡도를 보이지만, 평균적으로 충돌없이 잘 구현된 경우 O(1)만에 탐색이 가능하여 자주 사용됩니다.

9. 신장 트리(Spanning Tree)에 대해 설명하고, 최소 신장 트리를 찾는 알고리즘에는 무엇이 있는지 말해주세요.

• 신장 트리는 주어진 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프를 의미합니다. 이것은 그래프의 모든 정점을 연결하는 최소한의 간선을 가지는 부분 그래프라고 생각할 수 있습니다.
• 신장 트리의 특징: 정점의 수(주어진 그래프의 정점 수와 동일. 신장 트리에는 원래 그래프의 모든 정점이 포함됨), 사이클이 없음(신장 트리는 어떤 순환도 가지지 않아야 함. 어떤 정점에서 시작해서 다른 정점으로 돌아올 수 없어야 함), 연결성(신장 트리 내에서 어떤 두 정점을 선택해도 그 두 정점을 연결하는 경로(간선)가 존재해야 함)
• 크루스칼 알고리즘 (Kruskal's Algorithm): 크루스칼 알고리즘은 그리디 알고리즘의 일종으로, 가장 작은 가중치를 가진 간선부터 선택하여 최소 신장 트리를 구성합니다. 모든 정점을 개별적인 부분 집합으로 시작하고, 간선을 가중치 순으로 정렬한 후, 가장 작은 가중치의 간선부터 하나씩 선택하면서 사이클을 형성하지 않는 경우에만 해당 간선을 MST에 추가합니다. => 시간 복잡도: O(E log E) (E는 간선의 수)
• 프림 알고리즘 (Prim's Algorithm): 프림 알고리즘은 시작 정점에서부터 출발하여 트리를 확장해가는 방식으로 MST를 구성합니다. 초기에는 하나의 정점만을 포함하는 트리로 시작하고, 해당 트리와 연결된 간선 중에서 최소 가중치를 가진 간선을 선택하여 트리를 확장합니다. => 시간 복잡도: O(V^2) 또는 O(E + V log V) (V는 정점의 수, E는 간선의 수)
• 다익스트라 최단 경로 알고리즘은 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다.
• 크루스칼: 최소의 비용(최단거리) 모든 점을 다 연결할 때 사용(모든 점을 다 이은 경로가 최단 거리라고 말할 수 있지만 임의의 두 점 간의 거리가 최단 거리라는 보장은 없음)
• 다익스트라: 임의의 두 점 간의 최단 거리 구할 때 사용
  https://loosie.tistory.com/167#%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%8F%99%EC%9E%91_%EB%B0%A9%EC%8B%9D

10. 힙의 개념에 대해 설명하고, 힙에서 삽입과 삭제는 어떻게 이루어지는지 말해주세요.

• 힙(Heap)은 이진 트리 형태의 자료 구조로, 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 힙에는 두 가지 주요 연산인 "삽입(Insert)"과 "삭제(Delete)"가 있습니다.
• 삽입: 새로운 요소를 힙의 가장 하위 레벨에 추가합니다. 일반적으로 완전 이진 트리를 유지하도록 추가됩니다.
  => 삽입된 요소를 부모 노드와 비교하여 힙의 조건(최소 힙 또는 최대 힙)을 만족하도록 조정합니다. 최소 힙의 경우 새로운 요소는 부모 노드보다 작아야 하며, 최대 힙의 경우 크거나 같아야 합니다.
  => 조정이 완료되면 힙의 속성이 유지됩니다.
• 삭제: 일반적으로 최상단(루트 노드) 요소를 삭제합니다. 이 요소는 최소 힙에서는 가장 작은 값이고, 최대 힙에서는 가장 큰 값입니다.
  => 루트 요소를 삭제한 후, 힙의 가장 마지막 요소(가장 하위 레벨에서 가장 오른쪽에 있는 요소)를 루트로 이동시킵니다.
  => 이동된 루트 요소를 자식 노드와 비교하여 힙의 조건을 만족하도록 조정합니다. 최소 힙의 경우 자식 중에서 가장 작은 값을 가진 자식 노드와 비교하여 작아야 하며, 최대 힙의 경우 크거나 같아야 합니다.
  => 조정이 완료되면 힙의 속성이 다시 유지됩니다.
• 힙의 삽입과 삭제 연산은 각각 O(log n)의 시간 복잡도를 가지며, 이진 트리 구조를 유지하면서 요소를 추가하고 삭제하는 데 효율적으로 작동합니다. 이러한 특성으로 인해 힙은 우선순위 큐를 구현하는 데 매우 유용하게 사용됩니다.
  https://github.com/4z7l/tech_interview.zip/blob/main/%EC%A7%81%EB%AC%B4/DataStructure.md