블럭이 512 바이트로 이루어져있다고 하면, 0부터 511까지 1바이트씩 이루어져있는데, 1바이트는 각자의 주소를 가지고있다.(그걸 offset이라고 한다.)
디스크의 특정 지점을 읽으려면 섹터,블럭,offset을 알아야 한다.
참조 : https://velog.io/@seanlion/btree
B-Tree의 등장
디스크 I/O의 기본 단위는 블록입니다. 디스크로부터 데이터를 읽거나 기록할 때 이를 포함하는 디스크 블록 전체를 메모리로 읽어오고 다시 블록 전체를 디스크에 기록하는 방식으로 디스크 I/O가 일어납니다. 디스크에 접근하기 위한 시간은 다음과 같이 구할 수 있습니다.
Access time = seek time + latency + transfer time;
seek time : 디스크 헤드를 정확한 트랙 위로 이동시키는 시간
latency : 디스크를 회전시켜 해당 블록이 디스크 헤드 아래로 오게 하는 시간 (전체 접근 시간의 50%정도 차지)
transfer time : 디스크 블록을 메모리로 전송하는 시간
디스크 접근 시간 단위는 milli-second 단위인데, CPU로의 접근 시간은 mirco-second나 nano-second 단위입니다. 즉 디스크보다 CPU가 적어도 약 1000배~1000000배 정도 빠릅니다. 이렇게 느린 디스크 I/O를 수행하기 위해서는 색인(index) 구조가 필요합니다. 색인에 주로 쓰이는 것이 바로 *B-Tree 형제들(B트리, B+트리, R트리...)** 입니다.
예를들어 데이터베이스가 있고, Employee라는 테이블이 있다고 가정해 봅시다.
Employee (총 128 byte)
eid : 10byte
name : 50 byte
dept : 10byte
section : 8byte
add : 50 byte
데이터 베이스에는 100개의 record가 있는데, 1개의 record는 128byte입니다.
블록 1개가 512byte니까 1개의 블럭에 4개의 record를 넣을 수 있고, 디스크에 100개의 레코드를 넣으려면 총 25개의 블록이 필요합니다.
이 데이터베이스에서 특정 데이터를 찾으려면 현재 상황으로는 25개의 블록을 하나씩 다 찾아봐야 한다. 운이 없으면 모든 블록을 다 탐색해야 합니다.
그래서 빠른 탐색을 위해서 indexing을 해야 합니다. index에는 eid와 pointer 가 존재합니다. 각각의 pointer는 각각의 eid가 속한 레코드를 가리킨다.(레코드 포인터)
index 또한 디스크에 저장되어 있습니다. 단 데이터베이스와 따로 저장되어 있습니다. 100개의 인덱스를 저장하는데에는 4개의 블록이 필요하다.
이제 데이터 탐색을 할 때 인덱스에 접근합니다. 인덱스는 4개의 블록에 있으니까 4개의 블록을 탐색합니다. 그리고 특정 인덱스에서 포인터를 찾아서 그 포인터가 속한 블록으로 들어간다. 그러면 총 5개의 블록을 탐색하게 됩니다.
한 개의 블록에 32개의 인덱스가 들어가니까, 인덱스 of 인덱스에서 1번째 인덱스는 1번째 블록에 들어갈 진입포인트, 2번째 인덱스는 2번째 블록에 들어갈 진입포인트... 등으로 구성합니다.
인덱싱 of 인덱싱이 깊어지면 레벨이 생기게 됩니다. 그걸 트리형태로 표현하면 그게 B 트리의 원형이 됩니다. (이런 인덱싱 관리를 매번 수동으로 할 수 없으니 자동으로 self manage high level indexing을 하려고 한게 B트리)
B-Tree
B-트리는 일반적인 트리 구조인 이진 트리에서 확장되어 부모가 더 많은 수의 자식을 가질 수 있게 됩니다. M개의 자식을 가질 수 있도록 설계된 경우, M차 B-트리라고 합니다. 하나의 레벨에 많은 자료가 저장되기 때문에 전체적으로 트리의 높이가 줄어들게 됩니다. 트리의 높이가 줄어든다는 것은 곧 트리의 성능이 높아진다는 것을 의미합니다.(log단위로 성능의 단위가 붙습니다.) 또한 이런식으로 구성된 트리는 always 균형 잡힌 트리, always Balanced Tree 가 되어 검색에서든, 삽입에서든, 삭제에서든 항상 O(logN)의 성능을 보장합니다!
하나의 노드에 이렇게 많은 데이터를 가질 수 있다는 것은 대량의 데이터 처리가 필요한 검색 구조에 큰 장점이 됩니다. 대량의 데이터는 주로 외부 기억 장치에 저장되는데, 외부 기억 장치들은 블럭 단위로 입출력이 일어납니다. 즉 한 블럭이 1024바이트라면 2바이트를 읽어오기 위해서도 1024바이트를, 1000바이트를 읽어오기 위해서도 동일하게 1024바이트를 입출력 비용으로 지불합니다. B-트리는 하나의 노드를 한 블럭 크기 정도로 조절함과 동시에 트리의 균형도 맞춘 로직을 이미 갖추었기에 데이터베이스 시스템의 인덱스 저장 방식으로 유용하게 쓰입니다.
B-Tree의 성립 조건
노드의 데이터 수가 n개라면 자식 노드의 개수는 n+1개입니다.
노드의 자식노드의 데이터들은 노드 데이터를 기준으로 데이터보다 작은 값은 왼쪽 서브 트리에 큰값들은 오른쪽 서브 트리에 이루어 져야 합니다.
Root 노드가 자식이 있다면 2개이상의 자식을 가져야 합니다.
Root 노드를 제외한 모든 노드는 적어도 M/2 개의 데이터를 갖고 있어야 합니다. 3차 B-Tree 까지는 1개의 데이터를 갖고 있어야 하니 고려하지 않아도 되는 조건인것 같습니다. 4차 부터는 Root 노드를 제외하고 노드가 최소 2개의 데이터를 갖고 있어야 합니다.
다음과 같은 4차 B-Tree 에서 Root 노드의 데이터 8의 왼쪽 서브트리 노드가 데이터가 1개이므로 조건에 부합하지 않습니다.
Leaf 노드로 가는 경로의 길이는 모두 같아야 합니다. 즉 Leaf 노드는 모두 같은 레벨에 존재해야 합니다.
입력 자료는 중복될 수 없습니다.
B-Tree 탐색
B-Tree 는 이진트리와 마찬가지로 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 이루어져있습니다.
탐색 하고자하는 값을 root 노드 부터 시작해 하향식으로 탐색해 나갑니다.
B-Tree 삽입
차수에 따라 B-Tree 알고리즘이 다릅니다. 아래 예시는 3차(홀수) B-Tree의 예시입니다.
초기 삽입시에는 root 노드를 생성합니다.
데이터를 탐색해 해당하는 Leaf 노드에 데이터를 삽입합니다.
Leaf 노드 데이터가 가득 차 있으면 노드를 분리합니다. if(노드 데이터 개수 = M(차수))
insert7 에서 노드가 1, 5, 7 로 가득찼습니다.
정렬된 노드를 기준으로 중간값을 부모 노드로 해서 트리를 구성합니다.
분리한 서브트리가 B-Tree조건에 맞지 않는다면 부모 노드로 올라가며 merge합니다.
insert12 에서 [9, 7, 12] 를 서브트리로 분리 하였으나 B-Tree 조건에 맞지 않습니다.
Leaf 노드가 모두 같은 레벨에 존재 하지 않습니다.
Root노드와 merge로 조건을 만족시켰습니다.
B-Tree 삭제
삭제는 크게 Leaf노드인 경우와 Leaf노드가 아닌경우로 나누어집니다.
Case 1. 삭제할 노드가 Leaf 노드이며, 삭제하여도 B-Tree 구조를 유지하는 경우에는 그냥 삭제합니다.
Case 2. 삭제할 노드가 Leaf 노드이지만 ,삭제하는 경우 B-Tree 구조를 깨는 경우
Leaf노드에서 1을 삭제하면 B-Tree 구조가 깨집니다.
삭제한 노드의 부모노드로 올라가며 데이터를 가져옵니다.
1의 부무노드와, 형제노드를 merge 합니다. 부모 노드에서 자식노드로 값을 가져오고 자식노드의 형제노드와 merge 합니다.
root 노드 까지 올라가며 B-Tree 조건에 맞을때까지 이 작업을 반복합니다.
Case 3. Leaf 노드에 위치하지 않는 데이터를 삭제하는 경우
Leaf노드에 위치하지 않는 데이터를 삭제할 경우 입니다.
먼저, 노드에서 데이터를 삭제하고 왼쪽 서브트리에서 최대값을 노드에 위치시킵니다.
같은 방식으로 부모노드에서 자식노드로 값을 가져오고 형제노드와 merge 하며 B-Tree조건이 맞을때까지 반복합니다.
B+ Tree
B-트리는 특성상 순회 작업이 어렵습니다. B+ 트리는 색인구조에서 순차접근에 대한 문제의 해결책으로 제시되었습니다.
B-트리에서는 특정 key 값이 하나의 노드에서만 존재할 수 있지만, B+ 트리에서는 leaf 노드와 leaf의 부모 노드에서 공존할 수 있습니다. B+ 트리의 비단말 노드(not leaf)들은 데이터의 빠른 접근을 위한 인덱스 역할만 하기 때문입니다. (index set 이라 불린다)
그리고 leaf 노드들은 연결 리스트 형태로 서로 연결되어 있고 이를 순차집합(sequence set)이라고 하며 오름차순으로 정렬이 되어 있습니다.
고로 B+ 트리는 (기존의 B-트리 + 데이터의 연결 리스트)로 구현된 색인구조라고 할 수 있습니다.
B+ Tree의 특징
모든 key, data가 리프노드에 모여있습니다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가집니다.
모든 리프노드가 연결리스트의 형태를 띄고 있습니다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어듭니다.
리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같습니다. 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어납니다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용하였습니다.
B+ Tree의 탐색, 삽입, 삭제
탐색
B-Tree와 동일하게 탐색합니다. B-Tree와 다르게 Leaf 노드가 순차적으로 linked list를 구성하고 있어, 순차적 처리가 가능합니다.
삽입
삽입의 과정도 B트리와 매우 유사하지만 리프노드에서 최대 key개수를 초과할 때가 다릅니다.
Case 1. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리가 아닌 경우
B트리와 똑같은 삽입 과정을 수행합니다.
Case 2. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리인 경우
삽입 후 부모 key를 삽입된 key로 갱신하고, data를 넣어줍니다.
Case 3. 분할이 일어나는 삽입과정
분할이 일어나는 노드가 리프노드가 아니라면 기존 B트리와 똑같이 분할을 진행합니다. 중간 key를 부모 key로 올리고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정합니다.
분할이 일어나는 노드가 리프노드라면 중간 key를 부모 key로 올리지만, 오른쪽 노드에 중간 key를 포함하여 분할합니다. 또한 리프노드는 연결리스트이기 때문에 왼쪽 자식노드와 오른쪽 자식 노드를 이어줘 연결리스트 형태를 유지합니다. 해당 부분이 B트리의 분할과 다른 점입니다.
삭제
삭제과정 역시 기존 B트리와 유사합니다. 하지만 삭제할 key k는 무조건 리프노드에 존재하는 점, k를 삭제하기 위해 검색하는 과정에서 index에 존재할 수 있다는 점이 다릅니다.
Case 1. 삭제할 key k가 index에 없고, 리프노드의 가장 처음 key가 k가 아닌경우
기존의 B트리 삭제과정과 동일합니다.
Case 2. 삭제할 key k가 리프노드의 가장 처음 key인 경우
1) Index 부분은 다른 key 값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않습니다.
2) 재배치할 경우 index 부분의 node의 key 값은 변하지만 tree 구조는 변하지 않습니다.
3) 합병을 할 경우 index 부분에서도 key 값을 삭제합니다.
lksa4e
commented
3 years ago
B-Tree & B+ Tree
디스크 구조의 이해
참조 : https://velog.io/@seanlion/btree
B-Tree의 등장
디스크 I/O의 기본 단위는 블록입니다. 디스크로부터 데이터를 읽거나 기록할 때 이를 포함하는 디스크 블록 전체를 메모리로 읽어오고 다시 블록 전체를 디스크에 기록하는 방식으로 디스크 I/O가 일어납니다. 디스크에 접근하기 위한 시간은 다음과 같이 구할 수 있습니다.
디스크 접근 시간 단위는 milli-second 단위인데, CPU로의 접근 시간은 mirco-second나 nano-second 단위입니다. 즉 디스크보다 CPU가 적어도 약 1000배~1000000배 정도 빠릅니다. 이렇게 느린 디스크 I/O를 수행하기 위해서는 색인(index) 구조가 필요합니다. 색인에 주로 쓰이는 것이 바로 *B-Tree 형제들(B트리, B+트리, R트리...)** 입니다.
예를들어 데이터베이스가 있고, Employee라는 테이블이 있다고 가정해 봅시다.
Employee (총 128 byte)
eid : 10byte
name : 50 byte
dept : 10byte
section : 8byte
add : 50 byte
데이터 베이스에는 100개의 record가 있는데, 1개의 record는 128byte입니다.
블록 1개가 512byte니까 1개의 블럭에 4개의 record를 넣을 수 있고, 디스크에 100개의 레코드를 넣으려면 총 25개의 블록이 필요합니다.
이 데이터베이스에서 특정 데이터를 찾으려면 현재 상황으로는 25개의 블록을 하나씩 다 찾아봐야 한다. 운이 없으면 모든 블록을 다 탐색해야 합니다.
그래서 빠른 탐색을 위해서 indexing을 해야 합니다. index에는 eid와 pointer 가 존재합니다. 각각의 pointer는 각각의 eid가 속한 레코드를 가리킨다.(레코드 포인터)
index 또한 디스크에 저장되어 있습니다. 단 데이터베이스와 따로 저장되어 있습니다. 100개의 인덱스를 저장하는데에는 4개의 블록이 필요하다.
이제 데이터 탐색을 할 때 인덱스에 접근합니다. 인덱스는 4개의 블록에 있으니까 4개의 블록을 탐색합니다. 그리고 특정 인덱스에서 포인터를 찾아서 그 포인터가 속한 블록으로 들어간다. 그러면 총 5개의 블록을 탐색하게 됩니다.
멀티 인덱스
만약 레코드가 많아져서 1000개가 됐다고 생각해봅시다.
그럼 인덱스를 구성하는 블록의 개수도 40개로 많아지고, 인덱스 탐색의 효용이 작아집니다.
그런 경우에 인덱스를 위한 인덱스를 만드는 방법으로 해결할 수 있습니다.
한 개의 블록에 32개의 인덱스가 들어가니까, 인덱스 of 인덱스에서 1번째 인덱스는 1번째 블록에 들어갈 진입포인트, 2번째 인덱스는 2번째 블록에 들어갈 진입포인트... 등으로 구성합니다.
인덱싱 of 인덱싱이 깊어지면 레벨이 생기게 됩니다. 그걸 트리형태로 표현하면 그게 B 트리의 원형이 됩니다. (이런 인덱싱 관리를 매번 수동으로 할 수 없으니 자동으로 self manage high level indexing을 하려고 한게 B트리)
B-Tree
B-트리는 일반적인 트리 구조인 이진 트리에서 확장되어 부모가 더 많은 수의 자식을 가질 수 있게 됩니다. M개의 자식을 가질 수 있도록 설계된 경우, M차 B-트리라고 합니다. 하나의 레벨에 많은 자료가 저장되기 때문에 전체적으로 트리의 높이가 줄어들게 됩니다. 트리의 높이가 줄어든다는 것은 곧 트리의 성능이 높아진다는 것을 의미합니다.(log단위로 성능의 단위가 붙습니다.) 또한 이런식으로 구성된 트리는 always 균형 잡힌 트리, always Balanced Tree 가 되어 검색에서든, 삽입에서든, 삭제에서든 항상 O(logN)의 성능을 보장합니다!
하나의 노드에 이렇게 많은 데이터를 가질 수 있다는 것은 대량의 데이터 처리가 필요한 검색 구조에 큰 장점이 됩니다. 대량의 데이터는 주로 외부 기억 장치에 저장되는데, 외부 기억 장치들은 블럭 단위로 입출력이 일어납니다. 즉 한 블럭이 1024바이트라면 2바이트를 읽어오기 위해서도 1024바이트를, 1000바이트를 읽어오기 위해서도 동일하게 1024바이트를 입출력 비용으로 지불합니다. B-트리는 하나의 노드를 한 블럭 크기 정도로 조절함과 동시에 트리의 균형도 맞춘 로직을 이미 갖추었기에 데이터베이스 시스템의 인덱스 저장 방식으로 유용하게 쓰입니다.
B-Tree의 성립 조건
B-Tree 탐색
B-Tree 는 이진트리와 마찬가지로 작은 값은 왼쪽 서브트리, 큰 값은 오른쪽 서브트리에 이루어져있습니다. 탐색 하고자하는 값을 root 노드 부터 시작해 하향식으로 탐색해 나갑니다.
B-Tree 삽입
차수에 따라 B-Tree 알고리즘이 다릅니다. 아래 예시는 3차(홀수) B-Tree의 예시입니다.
B-Tree 삭제
삭제는 크게 Leaf노드인 경우와 Leaf노드가 아닌경우로 나누어집니다.
Case 1. 삭제할 노드가 Leaf 노드이며, 삭제하여도 B-Tree 구조를 유지하는 경우에는 그냥 삭제합니다.
Case 2. 삭제할 노드가 Leaf 노드이지만 ,삭제하는 경우 B-Tree 구조를 깨는 경우
Case 3. Leaf 노드에 위치하지 않는 데이터를 삭제하는 경우
B+ Tree
B+ Tree의 특징
모든 key, data가 리프노드에 모여있습니다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가집니다.
모든 리프노드가 연결리스트의 형태를 띄고 있습니다. B트리는 옆에있는 리프노드를 검사할 때, 다시 루트노드부터 검사해야 한다면, B+트리는 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 굉장히 줄어듭니다.
리프노드의 부모 key는 리프노드의 첫번째 key보다 작거나 같습니다. 그림의 B+트리는 리프노드의 key들을 트리가 가지고 있는 경우여서, data 삽입 또는 삭제가 일어날 때 트리의 key에 변경이 일어납니다. 해당 경우뿐만 아니라 data의 삽입과 삭제가 일어날 때 트리의 key에 변경이 일어나지 않게 하여 더욱 편하게 B+트리를 구현하는 방법도 존재하기 때문에 작거나 같다라는 표현을 사용하였습니다.
B+ Tree의 탐색, 삽입, 삭제
탐색
B-Tree와 동일하게 탐색합니다. B-Tree와 다르게 Leaf 노드가 순차적으로 linked list를 구성하고 있어, 순차적 처리가 가능합니다.
삽입
삽입의 과정도 B트리와 매우 유사하지만 리프노드에서 최대 key개수를 초과할 때가 다릅니다.
Case 1. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리가 아닌 경우
Case 2. 분할이 일어나지 않고, 삽입 위치가 리프노드의 가장 앞 key 자리인 경우
Case 3. 분할이 일어나는 삽입과정
분할이 일어나는 노드가 리프노드가 아니라면 기존 B트리와 똑같이 분할을 진행합니다. 중간 key를 부모 key로 올리고, 분할한 두개의 노드를 왼쪽, 오른쪽 자식으로 설정합니다.
분할이 일어나는 노드가 리프노드라면 중간 key를 부모 key로 올리지만, 오른쪽 노드에 중간 key를 포함하여 분할합니다. 또한 리프노드는 연결리스트이기 때문에 왼쪽 자식노드와 오른쪽 자식 노드를 이어줘 연결리스트 형태를 유지합니다. 해당 부분이 B트리의 분할과 다른 점입니다.
삭제
삭제과정 역시 기존 B트리와 유사합니다. 하지만 삭제할 key k는 무조건 리프노드에 존재하는 점, k를 삭제하기 위해 검색하는 과정에서 index에 존재할 수 있다는 점이 다릅니다.
Case 1. 삭제할 key k가 index에 없고, 리프노드의 가장 처음 key가 k가 아닌경우
기존의 B트리 삭제과정과 동일합니다.
Case 2. 삭제할 key k가 리프노드의 가장 처음 key인 경우
1) Index 부분은 다른 key 값을 찾는데 사용될 수 있기 때문에 leaf node의 값이 삭제되어도 삭제하지 않습니다.
2) 재배치할 경우 index 부분의 node의 key 값은 변하지만 tree 구조는 변하지 않습니다.
3) 합병을 할 경우 index 부분에서도 key 값을 삭제합니다.
참조 및 자세한 설명 : 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
B-Tree & B+ Tree 간단비교
공통점
모든 leaf의 depth가 같다
각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.
search가 비슷하다.
add시 overflow가 발생하면 split 한다
delete 시 underflow가 발생하면 redistribution하거나 merge 한다.
차이점
B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다. B+tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+tree에서는 data는 오직 leaf에만 존재한다.
B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.
B+ tree는 leaf node 끼리 linked list로 연결되어 있다.