CS
-
DB - TransactionCS/DB 2021. 2. 14. 22:42
Transaction 트랜젝션이란 데이터베이스에서 하나의 논리적 기능을 수행하기 위한 일련의 연산 집합으로서 작업의 단위이다. 다음과 같은 4가지 원칙을 만족한다. 원자성(Automicity): 트랜젝션의 연산은 DB에 모두 반영되던가, 전혀 반영되지 않아야 한다. 일관성(Consistency): 트랜젝션 작업이 종료된 후에도 일관성 있는 DB상태를 유지해야 한다. 독립성(Isolation): 한 트랜젝션이 작업하는 동안 작업중인 데이터를 다른 트랜젝션들이 접근하지 못하도록 해야 한다. 영속성(Durability): 트랜젝션의 실행이 성공적으로 완료된 후 결과는 영구적으로 반영되어야 한다. 격리수준(Isolation level) 동시에 여러 트랜젝션이 처리될 때 일관성 없는 데이터를 허용하는 수준을 말한..
-
DB - IndexCS/DB 2021. 2. 14. 20:18
DB - Index Index를 사용하는 이유 일반적인 테이블에서 데이터의 레코드는 내부적으로 아무런 순서 없이 저장된다. 이때 저장되는 데이터 영역을 Heap영역 이라고 한다. Heap에서는 인덱스가 없는 테이블의 데이터를 찾을 때 무조건 전체 데이터 페이지의 처음 레코드부터 끝 페이지의 마지막 레코드까지 다 읽어서(Full scan) 검색 조건과 비교한다. 그러므로 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어 두는 것이다. 즉 인덱스는 데이터를 select 할때 빨리 찾기 위해 사용된다. Index란? 테이블에 저장된 데이터를 빠르게 조회하기 위한 데이터 객체이다. index를 걸면 index를 거는 컬럼을 기준으로 새로운 객체를 생성하여 별도의 디스크 공간에 저장한다...
-
알고리즘 - 위상정렬CS/알고리즘 2021. 2. 14. 19:36
위상정렬 Topological Sorting 싸이클이 없는 유향 그래프의 순서를 위배하지 않도록 나열한 것이다. 모든 정점을 일렬로 나열하되 정점x 에서 정점y 로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치한다. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다. 위상정렬 알고리즘 진입 간선이 없는 정점을 하나 선택한다. 해당 정점의 진출간선과 해당 정점을 모두 제거한다. 구현 with JAVA 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public String topologicalSort(ArrayList[] list, int[] indegree) { Queue q = new LinkedList(); for(int i = 0; i
-
알고리즘 - 정렬CS/알고리즘 2021. 2. 13. 21:48
정렬 Selection Sort 최소 원소를 찾아 맨 왼쪽 원소와 교환하고 맨 왼쪽 원소를 제외한다. 하나의 원소가 남을 때까지 반복한다. 장점: 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적어 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용할 수 있다.(역순 정렬일때 가장 효율적이다.) 단점: 이미 정렬된 상태에서 자료가 추가되면 재정렬할때 최악의 처리 속도를 보인다. 수행시간: O(n^2) 구현 with JAVA 1 2 3 4 5 6 7 8 9 public void selectionSort(int[] arr) { for(int i = 0; i
-
알고리즘 - DFS, BFSCS/알고리즘 2021. 2. 12. 22:23
DFS, BFS DFS, BFS 그래프의 탐색 방법이다. 시간복잡도는 노드, 엣지의 개수에 영향을 받으며 DFS, BFS 동일하다. 인접 리스트로 구현시 -> O(|v|+|e|) 인접 노드로 구현시 -> O(v^2) DFS - 깊이 우선 탐색 재귀적으로 구현한다. 모든 노드를 다 탐색해야 최단 거리를 알 수 있으므로 최대 길이, 최대값 등을 찾을때 적합하다. 시작 노드로 부터 한 방향으로 계속 탐색을 진행하다가 더 이상 갈 곳이 없을때 되돌아와서 다른 방향으로 다시 탐색한다. 트리의 순회에서 중순위 탐색한 결과와 같다. 구현 with 자바 1 2 3 4 5 6 7 8 9 static void dfs(int[][] node, boolean[] memo, int num) { memo[num] = true; ..
-
DB - KEYCS/DB 2021. 2. 12. 20:33
KEY KEY 데이터베이스에서 조건에 맞는 튜플을 찾거나 검색할 때 기준이 되는 속성이다. Super Key 릴레이션을 구성하는 모든 튜플에 대해 유일성은 만족하지만 최소성은 만족하지 못한다. 유일성: 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있어야 한다. 최소성: 키를 구성하는 속성 하나를 제거하면 유일하게 식별할 수 없도록 꼭 필요한 최소의 속성으로 구성되어야 한다. Canditate Key 후보키: 유일성과 최소성을 모두 만족하는 모든 키를 의미한다. Primary Key 기본키: 후보키 중에서 선정된 것을 의미한다. Alternate Key 대체키: 후보키 중에서 선정된 기본키를 제외한 나머지 후보키를 의미한다. Foreign Key 외래키: 다른 릴레이션의 기본키를 참조하는 속성을 ..
-
DB - 파티셔닝과 샤딩CS/DB 2021. 2. 12. 20:23
파티셔닝과 샤딩 파티셔닝과 샤딩 서비스 크기 증가에 따른 DB 크기 증가하며 VLDB(Very Large DBMS)가 등장했고 여러 테이블을 관리하며 생기는 성능 이슈를 해결하기 위해 파티셔닝과 샤딩이 나왔다. 파티셔닝 큰 테이블이나 인덱스를 관리하기 쉬운 크기로 분리하는 방법이다. 장점 가용성: 물리적인 노드 분리에 따라 전체 DB내의 데이터 손상 가능성이 줄어들고, 데이터 가용성이 향상된다. 관리 용이성: 큰 테이블을 제거하여 관리를 쉽게 할 수 있다, 성능: 대용량 Data Write환경에서 효율적이며 특정 DML과 쿼리 성능을 향상시킨다. 단점 테이블 간 JOIN비용 증가 테이블과 인덱스를 별도로 파티셔닝 할 수 없고 함께 파티셔닝 해야 한다. 방법 Horizontal Partitioning(수평..