바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

B+ Tree

실제 데이터베이스의 indexing은 B+트리로 이루어져 있음

search에 있어서 매우~ 유리함.

- internal nodes: Index nodes (다음 노드를 가리킬 수 있는 포인터 주소가 존재)

- leaf nodes: Data nodes (실제 데이터)

1. 모든 key, data가 리프노드에 모여있음 (B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가짐)
2. 모든 리프노드가 연결리스트의 형태를 띄고 있음 (B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어듦)
3. 리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같음

*첫 번째 그림과 같이 leaf nodes가 linked list로 연결된 경우도 있음. 이 경우, 다른 leaf node에 접근하기 위해 다시 root를 방문하지 않아도 됨. 그러나 결국 background operation에 의한 비용을 감당해야하지만, 분명한 이득이 있음

Dis Friendliness of B+Tree

1. 페이지 기반 접근

B+tree는 데이터를 페이지 단위로 저장 (페이지는 일정한 크기의 데이터 블록)

페이지 기반 접근을 통해, 디스크에서 데이터를 읽거나 쓸 때마다 필요한 데이터만 읽거나 쓸 수 있음.

ex) 
데이터 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
이 데이터를 페이지 단위로 저장하면, 다음과 같이 3개의 페이지로 나눌 수 있음
```
페이지 1: 1, 2, 3
페이지 2: 4, 5, 6
페이지 3: 7, 8, 9, 10
```
이 경우, 디스크에서 데이터를 읽거나 쓸 때마다 필요한 데이터만 읽거나 쓸 수 있는데, 예를 들어, 데이터 2를 읽으려면 페이지 1만 읽으면 됨

2. 분산 저장

B+tree는 데이터를 루트 노드, 중간 노드, 리프 노드로 분산하여 저장함.

루트 노드는 메모리에 저장되고, 중간 노드와 리프 노드는 디스크에 저장됨.

루트 노드에는 데이터의 위치 정보가 저장되어 있기 때문에, 디스크에서 데이터를 찾을 때는 먼저 루트 노드에서 데이터의 위치 정보를 찾음.

예를 들어, 위의 데이터를 B+tree에 저장하면 다음과 같이 저장됨
```
루트 노드: 1, 4, 7
중간 노드 1: 2, 5, 8
중간 노드 2: 3, 6, 9, 10
리프 노드 1: 1, 2
리프 노드 2: 3, 4
리프 노드 3: 5, 6
리프 노드 4: 7, 8
리프 노드 5: 9, 10
```
이 경우, 디스크에서 데이터를 찾을 때는 먼저 메모리의 루트 노드에서 데이터의 위치 정보를 찾음. 데이터의 위치 정보를 찾으면, 해당 위치의 리프 노드에서 데이터를 찾을 수 있음.

3. 균형 잡힌 트리

B+tree는 균형 잡힌 트리이기 때문에, 데이터를 효율적으로 저장하고 검색할 수 있음. 균형 잡힌 트리는 트리의 높이가 낮기 때문에, 데이터를 찾기 위해 디스크를 읽거나 쓸 때 필요한 I/O 횟수가 적음.

출처

https://ssocoit.tistory.com/217

https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Plus-Tree

0. B Tree 시리즈의 효용에 대해서는 (아주) 간단히 아래 글에 정리해놓음

*하나의 노드에 여러 자료를 배치하며, 이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담음

https://lets-hci-la-ai-withme.tistory.com/190

*일반적으로 이진트리를 다룰 때, 하나의 노드에는 하나의 데이터가, 둘 이하의 자식 노드.

B-Tree(비 트리)

'균형' 이진 탐색 트리의 일종- 그러나 자식 노드를 2개 이상 가질 수 있음

핵심 성질 1: 하나의 노드가, 최대 M개의 자식을 가질 수 있음 (M차 B-Tree)

*internal nodes는 모두 2개 이상의 자식을 가져야 함

핵심 성질 2: 하나의 노드 내에, 2개 이상의 key(데이터)가 저장될 수 있음

M차 B-Tree는,

1. internal nodes의 자식 개수: ceil(M/2) ~ M개 - M값과 자식 개수의 관계

2. 각 노드 내 key의 개수: floor(M/2)-1 ~ (M-1)개 (항상 정렬된 상태, 중복 허용x)  - M값과 k의 관계

3. 한 노드 key의 개수 k에 따라, 그것의 자식 노드의 개수가 k+1로 결정됨 - k와 자식 개수의 관계

4. 특정 노드의 left subtree는 특정 노드 내 '모든 keys'보다 작은 값으로, right subtree는 큰 값으로 정렬

5. 모든 leaf nodes가 같은 레벨에 존재함

1) Search가 아주 쉽다 (하향식)

2) Insertion은 좀 복잡하다 (하향해서 적당한 leaf 자리 찾은 후 '적절한 상태'가 되기까지 상향)

case1: 분리가 일어나지 않는 경우 (상향 불필요)

case2: 분리가 일어나는 경우 (상향 필요)

3) Deletion은 더 복잡하다...

아주 훌륭한 레퍼런스들,,

https://code-lab1.tistory.com/217

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

https://escapefromcoding.tistory.com/731

메모리 계층 구조

- 메모리 계층 구조: 메모리를 필요에 따라 여러가지 종류로 나누어 둠, 상단으로 갈 수록 CPU가 빠르게 처리, 적은 양의 데이터, 비쌈

- 목적: CPU가 메모리에 더 빨리 접근하기 위함

CPU 내부: 레지스터 & 캐시

CPU 외부: RAM(주 메모리), 하드디스크, ...

프로세서(CPU)-메모리(RAM) 격차

CPU는 짧은 시간 내 여러 연산을 빠르게 처리함

CPU가 아무리 빨라도, (CPU 외부로 가서) 데이터를 가져오고 저장하는 속도가 느리면 전체 속도는 느려짐

이같은 격차를 줄이기 위해, 메모리에 효율적으로 접근하는 방법을 고민 → RAM이 연산하는 횟수를 최대한 줄이자

→ CPU 내부 레지스터 용량을 늘리지 못해도

→ CPU와 통합될 수 있는 빠른 보조 메모리를 만들자 = L1, L2 캐시 (레지스터와 RAM 사이에 위치, 속도와 용량이 중간.)

- L1 캐시; cpu 레지스터의 캐시

- L2 캐시; L1 캐시의 캐시

메모리 계층은 왜 피라미드일까?: 시간, 공간 지역성(Locality)

시간 지역성 (temporal locality) : 어떤 메모리주소에 접근한 경우, 곧 똑같은 주소에 다시 접근할 가능성이 높음
공간 지역성 (spatial locality) : 어떤 메모리주소에 접근한 경우, 곧 근처 주소에 접근할 가능성이 높음

- '시간'과 '공간'을 기준으로 이후에 접근할 가능성이 높은 메모리 주소들을 찾아내기 - 각각 for문, array

- 조만간 접근할 가능성이 높은 메모리 주소들을 미리 예측하고, 그 주소들을 CPU 내부에 미리 저장

- 접근 가능성이 더 높은 메모리 주소의 데이터를, CPU의 레지스터와 더욱 가까운 곳에 임시로 저장해 둠

- CPU가 찾는 메모리: 레지스터 > L1 > L2 > RAM... 순으로 찾아봄

Cycle?

여기서 'cycle'이 무슨 뜻일까?

- 사이클이란, CPU가 하나의 명령어를 처리하는 데 걸리는 시간

- CPU가 원하는 데이터에 액세스하기 위해 "한 바퀴"를 몇 번 돌아야 하는지

CPU Cycle

| Fetch | 메모리에서 명령어를 가져오는 단계 |
| Decode | 명령어를 해석하는 단계 |
| Execute | 명령어를 실행하는 단계 |
| Write Back | 명령어의 결과를 저장하는 단계 |

CPU Cycle을 도서관에서 책을 찾는 과정에 비유하자면...

• Fetch 단계: 책을 찾기 위해 도서관에 들어간다.
• Decode 단계: 책의 제목을 확인한다.
• Execute 단계: 책을 꺼내 읽는다.
• Write Back 단계: 책을 제자리에 꽂는다.

CPU Cycle의 길이는 CPU의 종류, 클럭 속도, 메모리 속도 등 다양한 요인에 따라 달라짐

CPU time = Clock cycles x Clock cycle time

CPU time = {명령어 개수(instruction count) x  명령어 당 cycle 횟수(CPI)} x Clock Cycle Time

*명령어의 수와 명령어 당 cycle 수로 표현 → 결국 명령어의 수와 명령어당 cycle 수를 줄이는 게 핵심

*Clock(클럭)에 대해 알기 위해서는 우선 회로에 대한 기본적인 이해가 있어야 함

쉽게 비유해 보자면, 사람이 살아가기 위해 심장에서의 펌핑이 필요하듯이 CPU 동작에 필요한 전압이 펌핑되는 것이라 보면 됨.

High-Low 상태가 반복되며 주기적으로 반복되는 이 신호를 이용해 CPU는 연산을 수행할 수 있음.

*CPU time이 적을 수록, 짧을 수록 더 성능이 좋음. 푸드 파이터도 더 짧은 기록이 나올 수록 좋음. 그럼 시간을 줄이려면 어떻게 해야 할까? 공식에 비춰서 생각해 보면, clock cycle(씹는 횟수)를 줄이고, clock cycle time(한 번 씹을 때 걸리는 시간)을 줄여야 함. 그러나 이게 실제로 가능할까? 결론은 "쉽지 않다." 이유는 두 가지가 trade off 관계에 있기 때문.

출처: https://skyjwoo.tistory.com/entry/컴퓨터-구조-CPU-time [jeongstudy:티스토리]

B-Tree, B+ Tree의 효용

- 내부 기억장치인 레지스터와 캐시는 CPU와 밀접한 위치에 있어 빠른 속도로 데이터를 처리할 수 있고,

- 외부 기억장치는 대용량 데이터를 효율적으로 저장하고 관리할 수 있는 구조로 설계되어 있음

"왜 많은 데이터베이스에서 B tree를 근간으로 사용할까?"

만약 아주 큰 사이즈의 데이터가 들어온다면 (ex. 1TB) 보통의 주요 메모리(RAM)은 8~32GB이므로, 해당 데이터를 레지스터나 캐시나 RAM에서 처리할 수 없음.

결국 CPU로부터 더 먼(? 사이클 횟수가 큰, 오래 걸리는) Flash Disk(SSD)나 하드드라이브에 데이터를 저장하게 됨. 이때 하드디스크나 SSD와 같은 외부 기억장치는 블럭(chunk)단위로 파일을 입출력함

이때 발생하는 입출력의 비용은 파일의 크기와는 상관 없이 동일함. (입출력에 있어 1KB짜리 블럭에 1byte짜리 알파벳 하나가 들어가 있어도 1KB가 꽉 차있는 블럭을 입출력하는 것과 차이 없음)

이때 하나의 블럭(chunk)에 여러 데이터들을 동시에 저장할 수 있다면 블럭을 보다 효율적으로 사용

=> B-트리, B+트리가 유용한 주요 이유

https://ssocoit.tistory.com/217 [코딩하는 경제학도]
Copyright © SsocoIT

refer to: https://joooing.tistory.com/entry/cs3

목적:  방향 그래프, 음의 가중치를 갖는 그래프에서 SSP를 찾는 것

DP 스타일.

- 모든 SP는 negative cycle 이 없을 때만 수행 가능

- 벨만 포드는, 다익스트라와 달리, 그래프 내에 negative edge가 있더라도 실행 가능 (심지어 negative cycle의 유무를 detect)

- |V|-1까지 단계를 진행했을 때 'single source로부터 그래프 내 모든 node의 최단거리'가 확정됨! (|V| = G 내 노드 개수)

- 정점의 개수만큼 모든 간선을 Relax

Why |V|-1?

source 제외한 각 노드 (총 |V|-1 개)에 대해, 그래프 내 모든 edge에 대한 연산 수행해야 함.

연산량 무려 O(|V||E|)

결국 정해진 source에 대한 특정 노드까지의 최단거리를 구해야 하는데, 해당 최단 거리는 더 작은 최단 거리들의 합으로 구성되어 있음.

source로부터 가장 멀리 떨어진 노드 간 연결하는 edge 개수는, 최대 |V|-1 이고, 각각은 최단거리들의 합임 (마치 optimal substructure). 따라서 

=> 최악의 경우일 때, 순환을 포함해서는 안되므로(negative cycle은 불가능, non-negative cycle은 최단 경로로 포함될 수 없음) 최대 V개의 정점을 가지고, 그 때의 간선의 개수가 V-1기 때문

Relax?

- δ(s,v) : source -> v까지 실제 최단경로 비용

- d[v] : source -> v까지 추정 최단경로 비용 (그래프 노드 안에 적힌 값으로 표현, node.d)

Relaxation:  d[v]가 δ(s,v)의 상한이 되도록 유지하고 조정하는 함수, 궁극적으로는 d[v]가 δ(s,v)까지 줄어들도록 조정함

v까지 최단거리 발견하면 그걸로 다시 업데이트! 또 업데이트!!! 반복쓰 ~.

벨만포드 전체 알고리즘 !

- Bellman-Ford 알고리즘은 정점의 개수만큼 모든 간선을 Relax하기 때문에 엄청난 연산

- 덕분에 음의 가중치가 있는 그래프의 단일 출발지 최단경로를 구할 수 있고, 그래프가 음의 순환구조를 갖는다면 이를 식별할 수 있음

구체적인 예시:

https://victorydntmd.tistory.com/104

Time-Analysis?

line 1 : theta(|V|)

그래프를 초기화

d[s] = 0, d[v] = infinite

line 2 ~ 4 : O((|V|-1)*(|E|)) = O(|V||E|)

정점의 개수만큼 반복문을 돌면서, 모든 간선에 대해 Relax를 수행

line 5 ~ 8: theta(|E|)

음의 가중치를 갖는 순환경로가 존재하는지 확인

존재한다면 false를 반환하고, 존재하지 않으면 벨만 포드 알고리즘이 잘 작동했다는 true를 반환

출처: https://victorydntmd.tistory.com/104

https://jeonyeohun.tistory.com/96

0과 1의 세상

- 컴퓨터는 0 또는 1이라는, 2진수 형태(binary)로 이해함

- 기본적으로, Byte(8개 단위의 Bit)를 사용함 

1비트: (0, 1) → 2^1

2비트: ((0, 1), (0, 1)) → 2^2 가지

3비트: 2^3가지

...

8비트: 2^8가지 = 256의 경우의 수

1 byte = 8 bits

1 KB = 2^10 bytes

1 MB = 2^10 KB = 2^20 bytes

1 GB = 2^30 bytes

1 TB = 2^40 bytes

1 KB부터는 2^10 배로 단위가 커짐!

refer: https://mindnet.tistory.com/entry/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-1%ED%8E%B8-Bit-%EC%99%80-Byte-%EC%B0%A8%EC%9D%B4%EC%A0%90

https://semiconductor.samsung.com/kr/support/tools-resources/dictionary/bits-and-bytes-units-of-data/

Data Types

char: 1 byte → express 256 values

short: 2 bytes

int: 4 bytes (32 bits) 

long: 8 bytes (64 bits)

string: an array of chars = an array of bytes(each byte: 0~255)

ASCII 코드

- 결국 컴퓨터는 모든 것을 0과 1의 조합(binary)로 읽음

- 컴퓨터에서 문자(영어 알파벳 / 숫자 / 특수 문자 / 제어 문자 / 공백 문자)를 binary로 표현하기 위한 표준 코드

- 문자와 binary를 일대일로 매핑 → 7비트(128가지) 또는 8비트(256가지)의 binary로 표현

- 아스키코드에서 10진을 보면.. 우리가 이해하기 더 쉬움.

아무튼 127까지 있는 걸 보니 문자를 7 bit로 할당(128가지의 문자를 binary로 매핑)

https://boycoding.tistory.com/250

 
모든 멤버 함수는 함수가 호출된 객체(인스턴스)를 가리키는 this 포인터를 가지고 있다.
호출된 객체의 주소를 가리키는 상수 포인터다.
상수 포인터 자료형이므로 포인터 자체가 다른 것을 가리키도록 할 수는 없다.
모든 과정은 컴파일러에 의해 자동으로 수행된다.
 
그러나, 명시적으로 this를 참조해야 하는 경우가 있다.
 
- 첫째, 멤버 변수와 이름이 같은 매개 변수를 가진 생성자(또는 멤버 함수)가 있는 경우, this를 사용해서 구분할 수 있다. 

class Something
{
private:
    int data;

public:
    Something(int data)
    {
        this->data = data;
        // this->data는 멤버 변수이고,
        // data는 매개 변수
    }
};

 
- 둘째, 클래스 멤버 함수가 작업 중이던 객체(인스턴스)를 반환하는 방식이 유용할 때가 종종있다. 이렇게 하면 같은 객체의 여러 멤버 함수를 연속해서 호출할 수 있는 방법이다.
만약 각각의 멤버 함수가 *this를 반환한다면 체이닝 기능이 있는 새로운 버전의 Calc를 만들 수 있다.

class Calc
{
private:
    int m_Value = 0;

public:
    Calc& Add(int value) { m_Value += value; return *this; }
    Calc& Sub(int value) { m_Value -= value; return *this; }
    Calc& Mul(int value) { m_Value *= value; return *this; }

    int GetValue() { return m_Value; }
}

int main()
{
    Calc calc;

    calc.Add(5).Sub(3).Mul(4); //함수 체이닝

    cout << calc.GetValue() << endl; // 8
    return 0;
}

출처: https://boycoding.tistory.com/250 [소년코딩:티스토리]

- recoloring이든 reconstruction이든, 부모를 검은 색으로!!!
 

레드블랙트리는, 자가 균형 이진 탐색 트리 중 하나이다.

Properties of Red Black Tree

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
4. 빨간색 노드의 자식은 검은색이다.
   == No Double Red(빨간색 노드가 연속으로 나올 수 없다)
5. 모든 리프 노드에서 Black Depth는 같다.
   == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다

 
레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다. 
이렇게 되면 4번 조건이 위배되는 상황이 발생한다. 즉, 빨간색 노드가 연속으로 2번 나타날 수 있다(Double Red)
 
레드 블랙 트리는 이러한 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.
 

새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자. 즉, 삼촌 노드는 말 그대로 부모의 형제라고 생각하면 된다. 
 
Double Red가 발생했을 때 

• 삼촌 노드가 검은색이라면 -> Restructuring을 수행하면 된다.
• 삼촌 노드가 빨간색이라면 -> Recoloring을 수행하면 된다.

Restructuring

1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다.
2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.

Recoloring

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
   1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
   1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

1-1) simple reconstruct 결과 root가 빨간색이 되어버린 경우

1-2) simple reconstruct 결과 부모 위에서 double red가 나타난 경우

-> double red가 나타난 지점 중 아래 노드를 기준으로, uncle을 살펴본다 (uncle이 검은 색이면 reconstruct, 빨간 색이면 recolor)
 

https://code-lab1.tistory.com/62

선형 자료 구조(연결 리스트, 스택, 큐 등): 순차적으로 요소에 접근

트리 자료구조는 노드들을 방문하기 위해 다른 방식을 사용해야 함

트리 순회(Tree Traversal): 트리의 모든 노드들을 방문하는 과정 - 주로 세 가지가 있음: 전위 순회, 중위 순회, 후위 순회

전위 순회와 후위 순회 모두 Recursion을 통해 간단하게 구현 가능.

특히, 두 순회는 print 코드가 Recursion 코드의 이전에 있는지 / 이후에 있는지에 따라 나뉨.

1. 전위 순회(Preorder Traversal)

: Work at a node is performed before its children are processed

2. 후위 순회(Postorder Traversal)

: Work at a node is performed after its children are processed

https://yoongrammer.tistory.com/70