코딩공장공장장

Q. Mysql InnoDB는 왜 이진트리가 아닌 Balanced Tree를 사용할까??Q. 자바의 Tree 자료타입은 왜 Balanced Tree가 아닌 균형이진탐색 트리인 RB 트리를 사용할까?? 이진트리를 학습하며 나는 위와 같은 궁금증이 생겼다.따라서 나는 이진트리, 이진탐색트리, 완전이진트리와 mysql innoDB의 balanced tree를 비교하며 어떠한 기준으로 자료구조가 선택됬는지 알아보았다. 내가 알아본 기준은 아래와 같다.[InnoDB에서 Balanced-Tree 사용하는 이유]균형 유지Fan-Out에 따른 탐색 횟수범위 검색[자바의 Tree 타입이 균형이진탐색 트리 사용하는 이유]메모리와 디스크의 차이단순한 구조와 쉬운 구현 균형유지우선 이진트리나 이진탐색트리와 Balanced-T..

레드블랙트리Red-Black Tree는 이진 탐색 트리의 한 종류로, 편향된 트리구조가 나올 수 있는 이진탐색트리를 균형을 유지하도록 하여 시간복잡도가 평균 O(logN)을 유지하도록 한 트리이다. 지난 포스팅에서 균형 이진탐색트리 중의 하나인 AVL 트리를 다루었다.AVL 트리와 비슷하게 회전연산을 사용하지만 컬러링이라는 새로운 개념이 존재하고,BF 기준으로 엄격하게 균형을 유지했던 AVL 트리에 비해 비교적 느슨한 규칙으로 균형을 유지하는 특성이 있다. AVL 트리에 비해 비교적 느스한 기준으로 인해 균형을 잡기 위해 수행하는 연산의 수가 적어 상대적으로 성능 또한 빠르다는 특징이 있어, 실무에서 가장 많이 사용되는 트리이며 자바의 TreeMap이나 TreeSet에서 사용되는 자료구조이다. 레드블랙..

AVL 트리AVL 트리는 이진탐색트리의 한 종류로편향된 트리구조가 나올 수 있는 이진탐색트리를 균형을 유지하도록 하여 시간복잡도가 평균 O(logN)을 유지하도록 한 트리이다. AVL 트리는 균형을 유지하기 위해 회전연산을 수행한다.LL 회전, RR 회전, LR 회전, RL 회전이라고 불리우는데, 회전 연산의 핵심 원리는 중간 값이 루트 노드가 된다는 것이다.LL, RR 등등은 노드의 왼쪽, 오른쪽 위치로 인해 붙여진 이름의 차이일 뿐,원리는 모두 할아버지, 부모, 자식이 있을 때, 중간 값이 루트가 되고 나머지 두 노드는 크기에 따라 왼쪽, 오른쪽에 위치하게 된다. BF(Balanced Factor, 균형인수)균형인수(BK) = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이균형인수는 AVL 트리가 트..

힙(이진힙)힙은 완전이진트리의 한 종류로최대값 기준으로 정렬된 최대힙과 최솟값 기준으로 정렬된 최소힙이 있다.최대힙은 부모노드가 항상 자식노드 보다 값이 크며 루트 노드에 최대값이 매핑되어있다.최소힙은 부모노드가 항상 자식노드 보다 값이 작으며 루트 노드에 최솟값이 매핑되어있다.정렬기준에 따른 첫번째 값이 루트 노드에 존재하여 우선순위 조회 탐색시에 사용된다.자바에서 우선순위 큐에 사용된 자료구조 또한 힙이다. [힙의 특징]완전 이진트리부모노드의 키값과 자식노드의 키값 사이에는 대소관계 성립키값 대소관계는 오로지 부모자식 간에 성립되며 형제 사이에는 대소관계가 없음 heapify힙이 규칙을 지키고 균형을 유지하기 위해 사용되는 연산이 heapify이다. 최대힙에서 heapify 연산이 어떻게 수행되는지 ..

트리트리란 노드와 간선으로 이루어진 자료구조로 부모노드에서 자식노드로 향하는 계층 구조를 이루고 있다.그래프의 한 종류이지만 트리는 사이클이 존재하지 않고 노드간 연결 경로는 부모에서 자식으로 오직 하나 뿐이라는 특징이 있다.트리에는 이진트리, 이진탐색트리, 완전이진트리가 존재한다. 선형구조로는 계층 구조를 사용하지 못하기에 트리라는 자료구조를 사용한다.대표적인 사용사례가 DB의 인덱스 페이지이다.책의 목차와 같은 계층 구조를 통해 데이터의 빠른 접근을 보장한다. 트리의 정의하나의 루트 노드가 반드시 존재루트 노드를 제외한 모든 노드는 부모노드를 갖음모든 노드는 0개 이상의 자식 노드를 가질 수 있음사이클이 존재하지 않음노드의 갯수가 N이면, 간선의 수는 N-1트리는 방향그래프? 무방향 그래프?그래프 이..

DNS(Domain Name System)도메인 이름을 IP 주소로 변환해주는 시스템 DNS의 구성요소도메인 네임 스페이스도메인에 해당하는 IP를 찾기 위해 사용하는 규칙(닷을 기준으로 계층적 구조를 이룸)네임 서버도메인 정보에 대응하는 IP를 관리하는 서버계층 구조로 이루어져 있으며 상위 계층은 하위계층의 IP주소를 반환하고 최하위 SLD에서 IP 주소를 반환함리졸버DNS Query를 DNS 서버에 요청하거나 응답을 캐싱 DNS 서버의 계층 구조[계층 구조에 따른 분류]1. Root DNS Server설명: DNS 계층 구조의 최상단에 있는 서버입니다.역할: 사용자가 요청한 도메인의 **최상위 도메인(.com, .net, .kr 등)**에 해당하는 **TLD 서버의 위치(IP)**를 알려줍니다.예시: ..