JH-Labs

데이터베이스에 인덱스가 없다면 테이블에 데이터가 삽입되는 순서는 특정 제약이 없다. 또한 데이터 조회 시(일반적인 where절 사용) 테이블 풀스캔이 발생한다. 이때 match 되는 데이터를 찾더라도 데이터 순회를 끝내는 것이 아니라, 테이블의 끝까지 데이터를 '순차 탐색'하면서 match 되는 데이터를 '모두' 찾는다. 이러한 테이블 풀스캔이 항상 나쁘다고 할 순 없지만 데이터가 많아질수록 성능에 문제가 발생할 것이다. 물리적으로는 한 테이블의 데이터 record들이 위와 같은 페이지 구조로 저장된다. 만약 record들을 특정 컬럼 기준으로 정렬해서 저장한다고 하면 테이블 풀스캔을 하지 않고도 찾고자 하는 데이터를 찾을 순 있지만 순차 탐색을 해야 한다는 단점이 존재한다. 이를 해결하기 위한 가장 대..

Balanced Tree (불균형) 이진탐색트리의 문제점은 최악의 경우 O(N)이 발생한다는 것이다. Balanced Tree는 항상 균형을 맞추어진 상태로 유지함으로써 O(logN)의 성능을 보인다. 하지만 데이터의 삭제, 삽입, 갱신이 발생할 때 Balance를 유지하기 위한 연산이 추가로 필요하게 된다는 단점이 있다. Balanced Tree의 종류로 AVL Tree와 레드블랙트리, 2-3 Tree, 2-3-4 Tree, B Tree 등이 있다. B-Tree는 다차원트리 B-Tree는 Balanced Tree이면서 다차원 트리이다. 하나의 노드가 가질 수 있는 자식 노드의 개수(링크 개수)를 M이라고 했을 때 하나의 노드에 '최대' M-1개의 자료를 담을 수 있으며 이 경우 M차 다차원 트리라고 한..

PCB(Process Control Block) 운영체제가 프로세스들을 관리하기 위해 사용하는 자료구조이다. 운영체제는 PCB 자료구조를 통해 프로세스 제어 및 관리(스케줄링, 종료, fork 등)를 한다. 아래 사진은 PCB가 갖는 데이터 구조이다. - process state : 프로세스의 상태(new ready waiting, running, terminated) - process number : PID - program counter : PC 레지스터 값(다음에 실행시킬 Instruction의 주소) - registers : 프로세스가 스케줄링되어 있던 CPU의 레지스터의 값(Context Switching시 사용됨) - memory-limits : 프로세스에 할당된 메모리 제한 정보(페이지 테이..

이번 포스팅의 목적은 네트워크 흐름의 overview를 그려보고는 것이다. 대략적인 흐름을 이해하는 것에 중점을 두었고 너무 자세한 내용은 생략했다. 1 계층 Physical Layer 컴퓨터가 다루는 / 주고받는 모든 데이터는 0과 1의 나열이다. Physical Layer에서는 0과 1의 나열로 구성된 데이터를 지정된 주파수에 맞게 흘려보내고 수신자는 이를 받아 디지털 신호로 디코딩한다. 주로 신호를 주고받는 역할을 담당하기 때문에 하드웨어 레벨에서 처리된다. 2 계층 Data-Link Layer 같은 네트워크 상에 존재하는 다양한 단말 중에 목적지로 보내기 위한 역할을 담당한다.(목적지를 연산한다는 것은 아님) 주로 Framing 작업을 수행하는데, 원본 데이터를 frame이라는 단위로 묶어 다음 ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

TreeMap - Key-Value로 이루어진 entry를 Tree에 저장하는 자료구조 - Key를 기준으로 '정렬'한 형태의 Tree임 (~이진탐색트리) - Tree중에서도 레드블랙트리를 기반으로 함(이진탐색트리에서 balanced tree) - 즉, 모든 노드에서 왼쪽 서브트리의 값은 오른쪽 서브트리의 값보다 작음 - HashMap보다 성능이 떨어짐 - 하지만 정렬된 상태로 Map을 유지하거나 Key에 대해 범위 탐색을 할 경우 HashMap보다 유리함 cf. Heap과 구분해야 하는데, Heap은 루트 노드가 가장 우선순위를 큰 값을 갖는 형태지만 정렬되어 있지는 않음 - 최소 힙에서 최대값을 삭제하는 연산은 O(logN) 이라고 착각하기 쉬우나, O(N) 이 소요됨 - 이유는 힙은 정렬되어 있지 ..

이진탐색트리(Binary Search Tree) - 최대 자식노드를 2개 갖는 이진트리 - 정렬된 상태로 유지되기 때문에 탐색 효율이 좋음 (중위순회시 정렬된 상태로 출력됨) - Balanced Tree가 아니기 때문에 극단적으로 모든 노드가 자식노드를 1개씩만 갖게 되면 O(n) 성능을 보임 Red-Black Tree - 이진탐색트리의 일종이지만 Balanced Tree이기 때문에 성능을 O(logN)으로 보장함 - 이진탐색트리의 일종이므로 왼쪽 서브트리의 모든 값은 오른쪽 서브트리의 모든 값보다 작아야 함(정렬됨) - Red-Black Tree는 이진탐색트리 중에서 성능이 가장 좋다. - 따라서 리눅스 커널의 프로세스 관리, Java 8이상 HashMap에서 해쉬 블록의 value, 함수형 프로그래밍..