안녕하세요.

오늘은 REST API에 대해서 포스팅 합니다.

REST 아키텍쳐를 웹 아키텍쳐중 하나인 HTTP 프로토콜과 동일 선상에서 해석하는 자료가 많았습니다.

재밌는 사실은 REST 창시자인 로이 필딩은 HTTP에 대해 전혀 언급하지 않았으며 순수하게 REST 시스템을 구성하는 방법에 대해서만 소개 하였습니다.

이번 포스팅의 목적은 웹과 무관한 REST 시스템을 본질을 이해하고, HTTP 프로토콜을 이용한여 REST 시스템을 설계하는 방법에 대해 이해하는 것 입니다.

REST

REST는 간단하게 말하자면, 존재하는 자원의 식별하고 제어하는 방법론 입니다.

REST 에서 정의 하는 자원에 대한 정의를 알아보고 자원의 제어 자원의 표현은 무엇인지 알아봅시다.

자원 (Resource)

자원이란 일이 처리되는 비용을 의미합니다.

REST 는 소프트웨어 아키텍쳐 이므로 컴퓨터의 자원을 의미합니다.

컴퓨터의 자원은 CPU가 수행하는 명령, 하드디스크에 저장되는 파일들, 메모리에 저장되는 데이터들을 의미합니다.

REST컴퓨터 자원을 사용하여 처리하는 한 단위의 작업을 식별할 수 있어야 합니다.

REST자원을 식별 할 수 있는 식별자가 필요합니다. 예를든다면 TIMESTAMP 나 UUID 같은 중복되지 않는 정보들을 식별자로 사용할 수 있습니다.

자원의 제어 (Resource Methods)

자원의 제어 는 흔히 CRUD 라 부르는 생성, 읽기, 변경, 삭제 행위를 자원에 수행하는것을 의미합니다.

이때 제어 방법은 일관적인 인터페이스로 구성되어야 합니다. 이는 소프트웨어의 API 처리 법칙을 정하면 일관적이게 규칙을 따라야 한다는 것입니다. 예를들어 웹 기반(HTTP)의 시스템에서 자원의 변경을 POST 메소드로 한다면(PUT이 더 어울릴지라도) 자원의 변경은 POST 메소드로 일관적이게 처리해야 한다는 점입니다.

자원의 표현 (Resource Representation)

자원의 표현은 조회한 순간의 자원 상태를 의미합니다. REST 시스템의 자원의 표현자기 서술적인(self-descriptive) 메시지와 HATEOAS(hypermedia as the engine of application state)로 구성됩니다. 이는 데이터를 설명하는 메타 데이터, 다음 자원으로의 이동을 안내하는 하이퍼 텍스트 등이 포함 되는 데이터를 의미합니다. REST 시스템은 클라이언트가 자원의 표현만 보더라도 이해되는 것을 목표로 합니다.


웹 기반(HTTP)의 REST

많은 자료들이 설명하고 있는 REST 시스템은 HTTP 기반으로 구성된 REST 시스템 입니다.

HTTP 기술을 통해 REST 시스템을 어떻게 구현하는지 알아봅시다.

자원의 식별

HTTPREST 시스템이 요구하는 자원의 식별URI의 정의로 처리합니다.

자원은 명사로 커뮤니케이션을 하기 때문에 많은 웹 기반 REST 시스템 선구자들은 URI을 명사구로 표현함으로써 자원을 나타내려고 노력했습니다.

다음과 같은 URI 표기법을 따릅니다.

  • URI의 세그먼트는 동사가 아닌 명사 사용.
    • users/mommoo/name (O)
    • users/mommoo/getName (X)
  • 만약 컨트롤 자원이라면 예외적으로 동사구 허용.
    • users/mommoo/name/duplicate (중복 이름 검사 API)
  • 자원의 관계가 표시되도록 작성.
    • users/mommoo/devices/android-phone
    위 예시는 유저 목록중 Mommoo를 의미하고, Mommoo가 가지고 있는 디바이스들을 의미하며, 디바이스들중 안드로이드 폰을 의미합니다.

자원의 제어

HTTP자원의 제어HTTP Method로 표현합니다. 대표적으로 POST, GET, PUT, DELETE 4개의 Method를 사용 합니다.

자원을 URI로 식별하고 URI에 행위를 붙여줌으로써 자원을 제어합니다.

아래는 자원 제어의 예시입니다.

  • GET users/mommoo/name (이름을 조회합니다.)
  • POST users/mommoo/name (이름을 등록합니다.)
  • PUT users/mommoo/name (이름을 수정합니다.)
  • DELETE users/mommoo/name (이름을 삭제합니다.)

자원의 표현

HTTP는 자원의 표현을 HTTP 응답 메시지로 구현합니다.

REST 자원의 표현의 특징인 self-descriptiveHATEOS를 만족하기 위해 ContentType 또는 커스텀 HTTP 헤더에 메타데이터 명시, 데이터에 링크를 포함하는 등의 기법을 사용합니다.

응답 예시는 https://slides.com/eungjun/rest#/79/0/1 참고해주세요.


REST-FUL

REST 시스템의 구성 요소는 다음과 같이 6개로 구성됩니다.

  • Client-Server
  • Stateless
  • Cacheable
  • Unitform-Interface
  • Layered-System
  • Code on demand (optional)

위 6가지 항목을 만족하는 HTTP REST 시스템을 구현한다고 가정할때, Unitform-Interface 항목을 제외한 나머지 항목들은 자연스럽게 구현이 되거나 조금만 신경을 쓴다면 어렵지 않게 구현할 수 있습니다.

Unitform-Interface 항목은 제외가 됬을까요? Unitform-Interface를 제공하기 위해 수행해야할 특징 중 self-descriptiveHATEOSHTTP 시스템에서 자연스럽게 처리 되지 않기 때문입니다.

사실 self-descriptiveHATEOS 속성은 데이터가 독립적으로 자생하기 위해 필요한 요소들이라 볼 수 있습니다. 그렇다보니 HTTP 서버 스펙을 구현할 때 데이터 독립적인 요소들까지 챙기지 않는 경우도 많습니다. 하지만 REST의 철학을 따르므로 REST 시스템이라 부르고 있습니다.

REST의 구성요소를 완벽하게 지키지 않은 REST 시스템을 구분하기 위해서인지 REST의 구성요소 (특히 Unitform-Interface)를 완벽하게 지킨 REST 시스템을 REST-FUL 시스템이라 부르고 있습니다.

로이 필딩은 REST 시스템의 규칙을 하나라도 제공하지 않는다면 REST 시스템이 아니라고 주장합니다.

정리하자면 REST 시스템으로 소개 되고 있는 시스템은 Unitfor-Interfaceself-descriptiveHATEOS가 지켜지지 않는 경우도 많으며, 나머지 항목까지도 완벽히 구현한 시스템을 REST-FUL 하다고 표현 합니다.


REST-API

API는 컴퓨터의 자원 제어 방법의 집합입니다.

그렇다면 REST-APIREST 시스템의 자원 제어 방법의 집합으로 정의할 수 있습니다.

한단계 더나아가 REST-FUL APIREST의 구성요소를 완벽히 따른 시스템의 자원 제어 방법의 집합이라 정의 할 수 있겠습니다.


오늘 포스팅은 여기까지 입니다.

읽어주셔서 감사합니다.

참고문헌

https://restfulapi.net/

그런 REST-API로 괜찮은가?

'네트워크' 카테고리의 다른 글

[네트워크] OSI 7계층  (0) 2021.07.26
[네트워크] HTTPS 프로토콜  (1) 2021.07.16

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

안녕하세요.

오늘은 데이터베이스 인덱스 개념에 대해 설명합니다.

인덱스란

인덱스(INDEX)DBMS의 검색 속도를 높이기 위한 기술 입니다.

DBMS는 데이터를 순차적으로 쌓으므로, 특정 데이터를 찾기 위해서는 데이터의 FULL-SCAN인 순차 탐색(O(N))이 필요합니다.

DBMS는 특정 데이터를 특별한 자료 구조로 쌓아 탐색 속도를 개선할 수 있는 기능을 제공합니다. 해당 기능을 인덱스라 부르고 쌓은 데이터들을 인덱스 테이블이라 부릅니다.

인덱스는 책의 목차와 비유할 수 있습니다. 우리가 책의 목차를 참고하여 필요한 내용으로 곧 바로 넘어가드시, DBMS인덱스 테이블에서 특정 인덱스를 찾아 필요한 행 데이터를 바로 가져옵니다.


인덱스 테이블

인덱스 테이블은 데이터를 조회할 때 사용되는 특정 컬럼의 데이터로 구성됩니다.

인덱스 테이블 에 포함된 데이터를 WHERE 문으로 조회를 하면 인덱스 테이블을 통해 ROW-ID를 빠르게 구한 뒤 단번에 행 데이터를 조회 할 수 있습니다.

인덱스 테이블 탐색

인덱스 테이블의 핵심은 빠른 조회 성능입니다. 이를 위해 인덱스 테이블은 탐색 트리 자료구조 중 하나인 B+트리 자료구조로 데이터를 저장합니다. 탐색 트리는 O(log2Nlog_2N) 성능의 빠른 조회를 할 수 있는 특징이 있습니다.

그렇기에, 데이터 FULL-SCAN[O(N)]성능에 비해, 압도적인 빠른 조회를 할 수 있는 장점 이 있습니다.

B+트리 포스팅을 참고해주세요.

인덱스 테이블 생성

TABLE을 생성 할 때, PRIMARY_KEY를 지정한 컬럼은 자동적으로 PRIMARY_KEY를 기준으로 인덱스 테이블이 생성됩니다.

만약 다른 컬럼을 인덱스 테이블을 생성하고 싶다면, 직접 생성해야 합니다.


인덱스 장점

인덱스의 장점은 곧 B+트리 자료구조의 장점과 일맥상통 합니다.

빠른 조회

인덱스 테이블은 메모리에 저장되어 있는 B+트리 자료구조 입니다.

메모리는 한정적인 자원이기 때문에 DBMS인덱스로 지정한 컬럼 데이터와 ROW-ID로 구성된 최소한의 노드로 B+트리를 구성합니다.

ROW-ID는 파일에 저장되어 있는 행 데이터를 가져올 수 있는 정보입니다.

여기에서 알 수 있는 재미있는 특징이 하나 있습니다. 데이터 FULL-SCAN이 느린이유는 순차탐색인 이유도 있지만, 빈번한 파일IO도 많은 영향을 미칩니다.

반면에 빠른 메모리 조회로 행 아이디를 찾는 인덱스 방식은 최소한의 파일IO를 사용합니다. 최소한의 파일IO는 더욱 빠른 탐색 속도를 가능하게 합니다.

데이터 정렬

만약 인덱스된 컬럼으로 정렬 명령을 내린다면 정렬 비용을 아낄 수 있습니다.

B+트리 구조상 조회된 데이터를 가져오기만 해도 정렬된 데이터를 획득할 수 있기 때문입니다.


인덱스 단점

지금까지의 설명만 보자면 인덱스 기능은 매우 훌륭한 기능 같습니다만, 그에 못지 않은 단점도 존재합니다. 대표적으로 아래와 같은 단점이 존재합니다.

  • 인덱스 테이블 유지 비용 (B+트리 유지비용)
  • 인덱스 테이블 추가 공간 비용

인덱스 테이블 유지 비용

B+트리의 중요한 특징 중 하나는 균형 이진 트리를 구성한다는 점 입니다. 노드의 삭제, 삽입시 트리 균형을 위해 트리 구조를 재구성 하는 비용이 발생합니다. 더군다나 탐색 이진 트리의 업데이트는 삭제 + 삽입 과정이 발생하므로 2배의 비용이 발생하게 됩니다.

위에서 살펴본 B+트리의 특징이 인덱스 테이블에도 똑같이 적용됩니다.

즉, O(log2Nlog_2N)으로 빠르게 조회가 가능하지만 삽입, 삭제, 업데이트 작업은 노드의 위치 탐색 비용 + 트리 재구성 비용 이 발생하게 됩니다.

DBMS는 트리 재구성 비용이라도 아끼기 위해 노드 삭제를 진행하지 않습니다. 대신 해당 노드에 사용하지 않는다는 마킹만 진행합니다. 그로인해 DBMS의 삭제, 업데이트 명령은 노드의 위치 탐색 비용만 발생하게 됩니다.

인덱스 테이블 추가 공간 비용

인덱스 테이블의 노드 삭제를 하지 않음으로써, 트리 재구성 비용을 아낀 전략은 유효해 보입니다. 하지만 이 역시도 다른 문제가 존재합니다.

그 문제는 바로, 인덱스 테이블이 거대해짐에 따라, 트리의 높이가 깊어지는 문제 입니다.

이는 테이블의 행 개수 보다 많은 개수의 저장공간을 필요로 합니다.

하지만 더욱 결정적인 문제는 트리 높이에 따른 성능으로 인해 인덱스 테이블 의 깊은 높이는 DBMS 성능을 점진적으로 내린다는 점 입니다.

결론적으로, 미 사용 노드를 트리에서 제거함으로써 높이 최적화가 필요함 을 알 수 있습니다. DBMS는 트리 높이 최적화를 수행하는 명령을 제공합니다. 해당 명령을 주기적으로 수행함으로써 전체적인 DBMS 성능을 높일 수 있습니다.


인덱스 생성 전략

위에서 살펴본 인덱스의 단점을 통해, 다음과 같은 결론을 도출 할 수 있습니다.

조회보다 삽입, 삭제, 업데이트가 더 많이 발생하는 테이블은 인덱스 기능이 오히려 단점이 될 수 있습니다.

또한 인덱스를 설정할 때는 유의할점이 몇개 존재합니다.

Cardinality 체크

인덱스를 구성할 땐, 컬럼의 Cardinality 를 고려하여 생성해야 합니다.

Cardinality 란 값의 분산도를 의미합니다. 다르게 표현하자면 값이 형태가 얼마나 다양하게 나올 수 있느냐의 척도입니다. 만약 (Y, N) 2가지 값으로만 구성된 컬럼을 인덱스로 설정하는 것은, 1700 페이지로 구성된 책에 목차가 2개만 존재하는것과 마찬가지 효과 입니다.

그렇기에 행 데이터가 최대한 많이 분류될 수 있는 컬럼으로 인덱스를 생성해야 효과적입니다.

조회 조건 빈번도 체크

당연한 얘기일 수 있겠지만, 조회 조건으로 자주 사용되는 컬럼일수록 인덱스 조건에 부합합니다.

아래의 항목은 간단한게 체크해볼 수 있는 리스트 입니다.

  • 조건절에 자주 등장하는 컬럼
  • LIKE 검색보다는 = 으로 검색하는 컬럼
  • ORDER BY 절에서 자주 사용되는 컬럼
  • JOIN으로 자주 사용되는 컬럼


지금까지 살펴본 내용을 요약하자면 다음과 같습니다.

  • 인덱스B+트리 구조를 통해 조회 성능을 올리는 기능입니다.
  • 데이터 FULL-SCAN은 빈번한 파일IO 작업을 통한 순차탐색으로 매우 느린 반면에 인덱스는 메모리에 저장된 트리 탐색을 통해 파일의 위치를 획득하여 파일IO 작업을 최소화 합니다.
  • 인덱스는 조회 성능을 높이고 삽입, 삭제, 업데이트 성능을 낮추는 트레이드 오프 기능 이므로 조회가 주된 목적인 테이블일 수록 유리합니다.
  • 인덱스는 조회가 주된 목적인 테이블일 수록 유리합니다.
  • 인덱스 테이블의 높이는 점점 깊어지므로, 주기적인 정리가 필요합니다.
  • 인덱스를 생성할 때는 Cardinality조회 조건 빈번도 체크가 필요합니다.

오늘 포스팅은 여기까지 입니다.

읽어주셔서 감사합니다.

'데이터베이스' 카테고리의 다른 글

[MySQL] 데이터베이스 원격 접속 명령어  (0) 2020.08.21
트랜잭션(Transaction)이란?  (27) 2017.02.27
Mysql 외부접근 설정하기.  (0) 2015.11.16

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

안녕하세요.

오늘은 B 트리 에 대해 포스팅 합니다.

B 트리이진 탐색 트리의 일종으로 탐색 성능을 높이기 위해 균형있게 높이를 유지하는 균형 트리 입니다.

균형 이진 탐색 트리는 대표적으로 RedBlackTree, AVL 트리 같은것이 있습니다. 두 트리가 독특한 규칙으로 높이를 유지 하는것처럼 B 트리도 자신만의 규칙이 존재합니다.

특이한점은, 이진 트리가 아니라는 점 입니다. 규칙에 따라 노드의 자식 노드 개수는 2개 이상이 될 수 도 있습니다.

B 트리 장점

B 트리의 장점은 크게 3가지가 존재합니다.

  • 균형 트리
  • 데이터 로드 효율성

균형 트리의 장점은 이진 탐색 트리 에서도 살펴봤다시피, 노드들이 한쪽으로 치우쳐 연결 리스트의 형태가 되는것을 방지하여 검색 효율을 높일 수 있다는 장점이 있습니다.

데이터 로드 효율성 측면은 대량의 데이터로 트리를 구성할 때, 진가를 발휘합니다.

데이터가 많은경우 메모리에 트리 구조를 유지하기 보다는 외부장치에 데이터를 저장해야 합니다. 각 노드의 값을 파일로 저장한 후, 파일 정보만 저장하고 있다면 메모리에서도 충분히 트리를 유지할 수 있게 됩니다.

외부장치에서 데이터를 읽어올때 데이터가 크던 작던 블럭 크기 만큼 읽어옵니다. 즉 노드의 데이터를 특정 블럭 크기 만큼 지정하여 저장 할 수 있다면 효율적으로 데이터를 읽어올 수 있다는 장점이 생깁니다.


B 트리 구성 방법

B 트리 만의 독특한 구성 규칙이 존재합니다. 이해를 위해서 모든 규칙은 맨 마지막에 정리하고, 중요한 조건순으로 차근차근 알아가봅시다.

N차 B 트리

B 트리를 구성할 때, 가장 중요한 조건은 노드가 최대 몇개의 데이터를 가질 수 있느냐 입니다.

만약 최대 3개의 자료를 가질 수 있다고 정의하면, 노드 자식 개수는 최대 4개를 가질 수 있습니다. 이때 최대 자식 개수를 사용하여 4차 B 트리 라고 표현 합니다.

즉 일반화 해본다면, 하나의 노드가 최대 M개의 자료를 가질 수 있다면 최대 자식 노드 개수는 M+1이 되므로 M+1차 B 트리 입니다.

왜 최대 자식 노드 개수가 M+1 이냐구요? 아래 B 트리 삽입 에서 살펴봅시다!

N차 B 트리는 노드의 최대 자료수는 N-1 이며, 최대 N개의 자식노드를 가질 수 있습니다.


B 트리 탐색

B 트리 탐색은 탐색 노드와 특징을 이용합니다.

특정 노드의 범위 위치를 찾은 후 아래의 자식 노드로 이동합니다.

아래의 과정은 0016 값을 찾는 과정입니다.

  • 루트 노드에서 0016 값의 범위 위치를 찾습니다. (0015 < 0016)
  • 다음 노드에 0016 값이 존재하는지 찾아봅니다. 존재하지 않으므로 0016 값의 범위 위치를 찾습니다. (0016 < 0017)
  • 다음 노드는 리프노드 이므로 해당 노드에 값이 존재하지 않는다면 트리에 값이 존재하지 않음을 알 수 있습니다. 0016 값이 있으므로 탐색을 종료합니다.


B 트리 삽입

B 트리의 차수를 정할 때 홀수냐 짝수냐에 따라 알고리즘이 조금 다릅니다. 홀수가 조금 더 계산하기 편하므로 홀수로 설명하겠습니다.

3차 B 트리 를 예시로 들어봅시다. (노드의 최대 자료 개수는 2개)

삽입의 핵심은 노드 분열 작업 입니다.

아래의 삽입 과정은 최초 노드 분열이 발생하는 과정입니다.

  • 01~02 번 삽입 과정은 루트 노드에 빈자리가 존재하여 자리를 찾아 삽입 합니다.
    • 데이터 저장 순서는 오름 차순으로 저장합니다.
  • 03번은 0011 을 루트 노드에 넣을 자리가 없는 경우 입니다.
    • 이때 B 트리 핵심 과정 중 하나인 노드 분열이 발생합니다.
    • 03-2. 루트 노드의 값들과 넣을 값을 포함하여 중간 값을 찾습니다. (홀수 차수를 고른것이 이때 편합니다.)
    • 03-3. 중간 값 0005 값을 부모 노드로 올리고, 왼쪽 값들과 오른쪽 값들을 자식 노드로 각각 구성하여 연결합니다.

아래의 과정에서 발생하는 노드 분열도 한번 살펴보시죠.

  • 04번 삽입은 탐색 노드 특징을 이용하여 리프노드 까지 도달합니다.
    • 리프노드에 자리가 비었으므로, 0017값이 그대로 저장됩니다.
  • 05-01. 0022 값의 자리를 탐색하여 리프 노드 까지 도달했습니다.
    • 05-01. 하지만, 리프 노드엔 자리가 없습니다. 노드 분열과 마찬 가지로 중간 값을 찾습니다.
    • 05-02. 중간 값을 부모 노드로 이동시킵니다. (노드 분열이 발생합니다.)
    • 05-02. 남은 값들은 각각 노드로 구성하여 중간 값 왼쪽, 오른쪽 자식노드로 연결합니다.

위 예시와 같이 리프노드에 공간이 부족할 때, 부모 노드로 중간 값을 옮기는 노드 분열를 수행하면 재밌는 특징이 생깁니다.

  • 규칙1. 노드의 자료가 최대 N개 라면, 해당 노드의 자식 노드 개수는 항상 N+1 입니다.
  • 규칙2. 모든 리프 노드들은 항상 같은 레벨에 위치하게 됩니다.
  • 규칙3. 노드의 자료가 최대 N개 라면, 리프 노드가 분열 할때 항상 중간 값으로 분열 하므로 노드의 자료 개수는 [N/2]~N개가 보장 됩니다.
    [3/2] ⇒ 2 (올림연산 입니다.)

마지막으로 아래의 노드 분열을 이해 하실 수 있다면, 트리 삽입 과정을 이해 하실 수 있습니다.


B 트리 삭제

B 트리의 삭제는 크게 두가지 케이스로 나누어 생각 해볼 수 있습니다.

  • 리프 노드에서 값 삭제.
  • 리프 노드가 아닌 중간 노드에서 값 삭제.

리프 노드에서 삭제

이 경우에도 크게 3가지 경우로 나뉩니다.

  • 리프 노드에서 값을 삭제 하더라도 최소 유지 개수 ([N/2]) 조건에 만족하는 경우.
  • 리프 노드에서 값을 삭제 할 때, 최소 유지 개수를 만족하지 못하지만 바로 옆 형제 노드들 중 최소 유지 개수 보다 많아 값을 빌려올 수 있는 경우.
  • 리프 노드에서 값을 삭제 할 때, 최소 유지 개수를 만족하지 못하고 옆 형제 노드들도 최소 유지 개수만 가지고 있어 값을 빌려올 수 없는 경우.

리프 노드에서 바로 삭제.

리프 노드가 최소 유지 개수를 만족하는 경우 바로 삭제가 가능합니다.

형제 노드에서 값을 빌려 오는 경우.

  1. 리프 노드형제 노드에서 빌려야 할 값을 찾습니다.
    • 오른쪽 형제 노드라면 형제 노드중 최대값.
    • 왼쪽 형제 노드라면 형제 노드중 최소 값.
  1. 리프 노드부모 노드에서 리프 노드형제 노드를 동시에 가리키고 있는 값을 찾습니다.
  1. 리프 노드에서 값을 삭제 후, 부모 노드에서 찾은 값을 리프노드로 내려주고 빌린 형제 노드 값을 부모 노드 찾은 값 자리에 넣습니다.

형제 노드에서도 값을 빌릴 수 없는 경우.

  1. 삭제할 리프 노드형제 노드를 병합 합니다. 병합 노드최소 개수 조건을 만족 시키기 위해 부모 노드에서 값 하나를 내려줍니다.
  1. 부모 노드도 최소 개수 조건을 만족하지 않는다면, 1번 과정을 리프 노드 대신 부모 노드로 치환하여 수행합니다.
  1. 만약 병합된 노드가 최대 개수를 넘는다면, 중간 값을 찾아 병합 노드의 부모 노드로 값을 넘겨줍니다.

중간 노드에서 삭제

해당 경우도 3가지로 나눌 수 있습니다.

  • 최소 개수 보다 많아 값을 빌려올 수 있는 자식 노드가 존재하는 경우.
  • 여유있는 자식 노드가 없지만, 부모 노드가 최소 개수보다 많은 경우.
  • 자식 노드도, 부모 노드도 여유가 없는 경우.

자식 노드에게 값을 빌려오는 경우.

  1. 값을 빌려올 자식 노드의 값을 찾습니다.
    • 왼쪽 자식 노드라면 최소 값을 찾습니다.
    • 오른쪽 자식 노드라면 최대 값을 찾습니다.
  1. 타겟 노드의 값을 지우고, 해당 자리를 찾은 자식 노드의 값으로 대체 합니다.

여유있는 자식 노드는 없지만, 부모 노드가 여유가 있는 경우.

  1. 노드의 삭제 값의 자식 노드들을 합병합니다.

자식노드, 부모노드 둘다 여유가 없는 경우.

  1. 노드의 삭제 값의 자식 노드들을 병합합니다.
  1. 노드의 형제 노드부모노드를 대상으로 병합을 진행합니다.
  1. 만약 병합 노드가 최대 개수를 초과 한다면 중간 값을 추출해 병합 노드부모노드로 이동시킵니다.


B+트리

B 트리의 단점은 순회?

Warning!! 주관적인 생각이 섞여 있습니다.

B 트리 는 자료 순회가 단점이라는 글이 많습니다. B 트리도 트리 구조이기 때문에 트리 순회와 똑같은 시간복잡도가 걸립니다. 그렇기에 단점이라 할 수는 없습니다.

많은 자료들이 단점이라 오해(?)하는 이유는 트리 순회를 개선한 B+트리의 존재 유무 때문이 아닐까 생각이 듭니다.

리프 노드들을 모든 노드의 값이 포함되도록 처리

B+ 트리의 순회 연산의 개선 포인트는 리프 노드들의 구조에 있습니다.

다음의 예시를 보면, 리프 노드들은 모든 값들을 포함하고 있고 연결리스트 형태를 구성하고 있습니다.

리프 노드의 위 노드들은 검색을 위해 유지하고 있는 모습입니다.

특정 범위를 순회하고 싶다면, 손쉽게 특정 리프 노드에서 차례대로 순회 할 수 있습니다.

빠른 검색-삽입-삭제 + 범위 검색 이 필요한 관계형 데이터베이스가 해당 자료구조를 사용하고 있습니다.


B 트리의 삽입, 삭제 과정을 단번에 이해하긴 어려운거 같습니다.

더군다나 트리의 특정 스냅샷 기준으로 설명했기 때문에 높이가 큰 트리인 경우에는 설명한 개념에 더해 재귀 개념 까지 합산하여 이해를 해야 하기 때문에 더 어려운거 같습니다.

B 트리 특징들을 살펴보면서 항상 만족했던 조건들을 다시 정리해보면 아래와 같습니다.

  • N차 B 트리는 노드의 최대 자료수는 N-1 이며, 자식노드는 최대 N개.
  • 노드의 자료가 최대 N개 라면, 해당 노드의 자식 노드 개수는 항상 N+1.
  • 노드의 자료가 최대 N개 라면, 노드의 자료 개수는 [N/2] ~ N개. (루트 노드 제외)
  • 모든 리프 노드들은 항상 같은 레벨에 위치한다.

오늘 준비한 포스팅은 여기까지 입니다.

읽어주셔서 감사합니다.

'자료구조' 카테고리의 다른 글

[자료구조] 이진탐색트리  (1) 2021.07.12
[자료구조] 트리(Tree)  (0) 2021.07.10

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

안녕하세요.

오늘은 OSI 7계층에 대해 간략하게 소개합니다.

OSI 7 Layer

OSI 7계층 이란 네트워크 통신을 수행할 때, 처리되어야 할 작업을 순차적으로 7단계로 처리 하는 과정을 의미합니다.

계층을 나누어 처리함으로써, 필요한 작업들은 독립적인 모듈로 처리 됩니다. 이는 디버깅이 용이하고 모듈간 교체 및 확장등이 자유롭다는 장점이 존재합니다.

OSI 1~3 계층하드웨어 영역으로써, 각 층마다 매칭되는 하드웨어 장치가 존재합니다. 따라서, 해당 계층의 역할들은 하드웨어가 실질적으로 수행하는 역할 입니다.

OSI 4~7 계층소프트웨어 영역이며, 4~6 계층OS7계층은 우리가 사용하는 프로그램이 해당 계층의 역할을 수행합니다.

다음 이미지는 OSI 7계층 구성도 입니다.


Physical Layer

네트워크 통신은 서로 멀리 떨어져 있는 지점끼리 데이터를 주고 받을 수 있습니다. 데이터 통신은 아날로그 신호(주파수)로 최초 전달 되고 디지털 데이터로 변환되어 해석하는것을 의미합니다.

물리 계층(Physical Layer)은 이러한 아날로그 신호(주파수)를 디지털 신호로 변경해주는 역할을 수행합니다.

물리 계층의 역할은 여러 하드웨어의 조합으로 수행됩니다. 아날로그 신호를 디지털 테이터로 변환하는 주된 역할은 NIC(Network Interface Controller)란 하드웨어가 수행합니다. 흔히 네트워크 카드, 랜 카드로 불립니다.

Data-Link Layer

네트워크 통신은 여러 프로그램이 동시적, 지속적으로 수행 할 수 있습니다. 이때, 컴퓨터는 들어온 데이터를 식별하기 위한 라벨링 작업이 필요합니다. 이러한 행위를 프레임화 라고 부릅니다.

데이터 링크 계층(Data-Link Layer)프레임화를 진행하고, 만들어진 프레임을 상위 계층 또는 하위 계층에 전달 합니다.

결론적으로, 해당 계층은 두가지 역할로 정리할 수 있습니다.

  • 프레임화 (데이터 라벨링)
  • 흐름제어 (상위 계층 또는 하위 계층으로 프레임 전달)
    3계층, 1계층도 하드웨어 영역이므로 인접한 네트워크 장비에 데이터를 전송하는것을 의미합니다.

해당 계층의 역할을 수행하는 대표적인 하드웨어는 위에서 언급한 NIC 입니다. 해당 계층의 역할을 전문적으로 수행하는 브릿지, 스위치 같은 장비들도 존재합니다.

Network Layer

물리 계층의 아날로그 신호는 거리가 먼 지점까지 전달되지 않습니다.

신호를 세게 하는 리피터라는 장비를 사용 할 수 있지만, 이는 특정 지점에 전달 하기 보다 무분별하게 전파하기 때문에 효율이 떨어 집니다.

이를 해결하기 위해 사용되는 장비는 바로 라우터 입니다. 무분별하게 전파하는 리피터와는 다르게 라우터는 내장된 라우팅 알고리즘을 통해 전달 할 수 있는 가장 가까운 라우터 까지의 경로를 결정하고 이를 테이블로 저장합니다. 해당 행위를 라우팅 이라 표현 합니다.

경로가 결정되면 전달해야할 데이터를 다음 라우터에게 맡깁니다. N개의 라우터가 지속적으로 정보를 전달을 하면서 최종 목적지 까지 전달하는 방법을 포워딩 이라 표현 합니다.

이때, 정보를 전달 받은 라우터는 본인이 최종 목적지 인지 여부와 응답 데이터를 다시 출발지 라우터로 보내기 위한 데이터가 필요합니다. 즉 전달해야 하는 데이터는 출발지 정보, 목적지 정보가 부가적으로 필요 하며 해당 정보는 IP 라는 정보로 처리합니다. 전달 데이터에 IP 정보를 붙인 데이터를 패킷 이라 부릅니다.

정리하자면 해당 계층은 3가지 역할을 수행합니다.

  • 2계층에서 넘어온 데이터를 패킷으로 만들거나, 수신된 패킷 데이터를 해석합니다.
  • 다음 라우터의 경로를 찾기 위한 라우팅을 진행합니다.
  • 패킷 전달의 역할을 다음 라우터에게 위임하는 포워딩을 진행합니다.

해당 계층에 대표적인 하드웨어는 위에서 언급했던 라우터 이며 우리가 집에서 흔히 사용하는 공유기라우터의 역할을 어느정도 수행 합니다.

Transport Layer

데이터 통신은 여러 프로그램이 동시에 지속적으로 수행되고 있습니다.

그렇기에 특정 데이터가 어떤 프로그램과 관련이 있는지 식별할 수 있어야 합니다.

식별하기 위해 포트번호 라는 데이터가 사용됩니다.

전송 계층(Transport Layer)은 하위 계층에 데이터를 전달 할때 데이터에 포트번호를 붙이며, 하위 계층으로 부터 데이터를 전달 받을 때도 포트번호 를 통해 데이터를 식별합니다.

또한 데이터 통신 프로토콜에 따른 알고리즘이 수행됩니다. 대표적인 예로 TCP, UDP 프로토콜이 존재합니다.

TCP 통신이 제공하는 연결지향, 흐름제어, 오류검출 및 회복 등이 해당 계층에서 수행됩니다.

해당 계층의 역할은 운영체제 커널에 소프트웨어적으로 구현되어 있습니다.

정리하자면 해당 계층은 크게 2가지 역할을 수행합니다.

  • 포트번호를 통한 데이터 식별 작업.
  • 데이터 통신 프로토콜에 따른 알고리즘 수행.

Session Layer

Warning! 해당 계층은 작성자가 정확히 이해하지 못했습니다.

세션 계층(Session Layer)의 주된 목표는 각 프로그램의 네트워크 통신 상태 관리동기화 입니다.

상태 관리는 데이터 통신 프로토콜 알고리즘이 가지는 특성들을 수행하기 위해 필요한 처리를 의미합니다. 예를들어 TCP 프로토콜은 연결 수립, 종료와 같은 상태 등을 처리합니다.

동기화전송 계층에서 올라온 또는 응용 계층 에서 내려온 데이터를 안정적으로 상위 또는 하위 계층으로 전달하는 역할을 수행합니다. 데이터가 성공적으로 전달된 지점까지 내부적으로 마킹해두며, 데이터 전달에 문제가 발생하면 마킹한 지점부터 오류지점까지 데이터 복구 절차가 수행됩니다.

해당 계층 역할도 운영체제가 수행합니다.

Presentation Layer

표현 계층(Presentation Layer)은 하위 계층이 전달한 데이터를 어플리케이션이 해석 할 수 있도록 데이터를 디코딩 하거나, 데이터 전달을 효율적으로 수행하기 위해 데이터를 인코딩 한 뒤 하위 계층으로 전달합니다.

다음은 표현 계층이 수행하는 대표적인 예시 입니다.

  • SSL 프로토콜에서 처리되는 암, 복호화 처리
  • 데이터 압축해제 처리
  • 데이터 포맷(UTF-8 과 같은)에 따른 인코딩, 디코딩 처리

해당 계층 역할 역시 운영체제가 수행합니다.

Application Layer

응용 계층(Application Layer)은 요구사항을 처리하기 위해 네트워크 통신을 이용한 데이터의 송-수신이 발생하는 가장 마지막 영역 입니다.

운영체제는 전송 계층에서 제공하는 API를 활용하여 네트워크 통신을 가능토록 API를 제공하는데, 이를 소켓 API라 부릅니다.

해당 계층은 소켓 프로그래밍을 통해 데이터를 송신 및 수신을 수행합니다.

재밌는 특징은 각 프로그램이 개별적으로 데이터 규격을 만들어 통신 할 수 있습니다. 데이터의 인코딩 및 디코딩을 각 프로그램이 자체적으로 수행할 수 있기 때문입니다.

프로그램이 대표적으로 사용하는 데이터 규격은 HTTP 프로토콜 방식이 있으며 작은 단위로는 JSON, XML과 같은 데이터 규격도 존재합니다.

해당 계층의 역할은 개발된 프로그램이 수행합니다.

TCP/IP 모델의 등장

독립적인 모듈을 구성하는것은 정답이 존재하지 않습니다. 나뉘어진 모듈이 서로 심하게 의존하는 경우 모듈의 결합도가 높다고 하며, 모듈이 너무 작은 단위로 구성 된 경우 응집도가 떨어진다고 합니다. 이러한 특징들은 소프트웨어적 가치를 하락시키는 요인입니다.

OSI 7계층은 대표적인 네트워크 통신 규격으로 사용 되고 있지만, OSI 7계층역시 결합도가 높고, 응집도가 낮은 모듈들이 존재합니다.

그 대상 계층들은 응용 계층, 표현 계층, 세션 계층 입니다. 따라서 현대적인 네트워크 통신 규격인 TCP/IP 모델 은 다음과 같이 정의 되었습니다.

TCP/IP 모델네트워크 엑세스 계층데이터 링크 계층 + 물리 계층 으로 나누어서 표현하기도 합니다.

반면에 응용 계층, 표현 계층, 세션 계층 들은 응용 계층 하나로 통합 되었습니다.


TCP/IP 모델의 각 계층 역할도 OSI 7계층의 역할과 동일합니다.

몇몇 모듈이 독립적으로 수행되던 역할이 하나의 모듈이 통합 수행 한다고 이해하면 될거 같습니다.

오늘 포스팅은 여기까지 입니다.

읽어주셔서 감사합니다.

'네트워크' 카테고리의 다른 글

[네트워크] REST API  (0) 2021.08.08
[네트워크] HTTPS 프로토콜  (1) 2021.07.16

포스팅이 도움 되셨다면, 커피 한잔 후원해주세요!
더 좋은 포스팅 작성에 큰 힘이 됩니다.

Buy me a coffeeBuy me a coffee

+ Recent posts