B-Tree

• b-Tree 롼?

🏗️ Build Up

• 바이너리 서치

• 특징
• 탐색시간이 평균적으로 log(n)으로 빠르다라는 특징을 갖지만, 한쪽으로 치우쳐져 있는 경우라면 n의 시간 복잡도를 갖는 단점이 있다. (편향트리 1,2,3,4,5,6 일떄, 6,5,4,3,2,1 인 경우)

💨What

B-Tree란?

• 특히나, BinarySearch 보다 탐색시간이 빠르다는 장점을 가지고 있다. 최악의 경우를 포함해 Log(n)이라는 시간복잡도를 갖는다.

특징

• 노드에 키와 데이터를 가지고 있다.

• 단점
• 균형을 이루는 데에는 추가적인 비용이 필요하다 ( 삽입, 수정, 삭제의 반복을 통해 균형을 맞추기 위한 행위가 필요하기 때문)

❓Why [왜 B-Tree는 빠른가?]

✅ Diff B+Tree

• B+Tree는 B-Tree와는 다르게 노드에 키값만 저장하고 있는다는 특징이 있다. 그럼으로써 리프노드에는 서로다른 데이터 끼리 연결리스트로 연결되어 있다.

• 장점
• 데이터의 저장 공간을 더 사용할 수 있다.
• 같은 페이지 메모리에서 더 많은 노드들을 수용할 수 있게되는 것이다.
• 그러므로 tree의 depth 또한 줄어지게 되는 장점이 있다.
• 리프노드의 연결리스트로 이루어져 있어 범위 탐색이 매우 용이하다.
• 왜냐하면 기존의 B-Tree는 루트노드를 기점으로 지속적으로 탐색을 해야 하기 때문이다.
• B+Tree는 해당 시작 지점으로 부터 끝 지점까지 탐색으로 해당 범위를 전부 탐색하기 때문에 이점에서는 B+Tree가 더 빠르다.
• 삭제 작업이 B-Tree에 비해 쉬운 장점이 있다.
• 네부 노드에서 값을 제거할 필요가 없기 때문이다.
• B+Tree에는 동일한 값이 반복된다. B-Tree에서는 각 값이 고유하하다

• 단점
• 오히려 루트에 가까운 대상을 찾을 떄 B-Tree보다 탐색이 느리다.
• 왜냐하면 B+Tree는 링크드 리스트로 연결된 단말노드의 깊이까지 무조건적으로 탐색하기 때문이다.

📌 REFER

• 한국

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

B-tree는 인덱스를 이루고 있는 자료구조의 일종이다. B-tree에서 'B'는 정확히 어떤 의미라고 밝혀진 바는 없다. 아마 'Balanced'를 의미하는 'B'가 아닐까라는 추측만 있다. MySQL의 DB engine인 InnoDB는 B+tree 로 이뤄져있는데, B-tree의 확장된 개념 이다. 먼저 B-tree 를 살펴보자. 트리 구조의 우위성 트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다.

https://zorba91.tistory.com/m/293

[DB] 11. 인덱스(Index) - (1) 개념, 장단점, B+Tree 등

1. 인덱스(Index)란? 2. 인덱스(Index)의 장단점 3. 인덱스를 사용하면 좋은 경우 4. 인덱스의 자료 구조 인덱스(Index)는 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조 이다. 테이블의 특정 컬럼(Column)에 인덱스를 생성하면, 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다. 컬럼의 값과 물리적 주소를 (key, value)의 한 쌍으로 저장한다.

https://rebro.kr/167

[자료구조]이진 탐색 트리(Binary Search Tree)

이진 검색 트리란 이진 탐색과 연결리스트를 결하한 자료구조입니다. 이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 삽입과 삭제가 가능합니다. 이진 탐색의 경우 탐색에 소요되는 시간 복잡도는 O(logn)으로 빠르지만 자료 삽입, 삭제가 불가능하고, 연결리스트의 경우 자료 삽입, 삭제에 필요한 시간 복잡도는 O(1)로 효율적이지만 자료 탐색에 필요한 시간복잡도는O(n)이 됩니다.

https://junk-s.tistory.com/35

[MySQL] B-tree, B+tree란? (인덱스와 연관지어서)

B-tree는 인덱스를 이루고 있는 자료구조의 일종이다. B-tree에서 'B'는 정확히 어떤 의미라고 밝혀진 바는 없다. 아마 'Balanced'를 의미하는 'B'가 아닐까라는 추측만 있다. MySQL의 DB engine인 InnoDB는 B+tree 로 이뤄져있는데, B-tree의 확장된 개념 이다. 먼저 B-tree 를 살펴보자. 트리 구조의 우위성 트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다.

https://zorba91.tistory.com/293

• 외국

All About Indexes Part 2: MySQL Index Structure and Performance

Database indexes speed up data retrieval operations. But there is a price we pay for these benefits. In this article, we'll focus on the structure behind the MySQL index. We'll also measure database performance by using large datasets to test two versions of the same database - one with indexes and the other without them.

https://www.vertabelo.com/blog/all-about-indexes-part-2-mysql-index-structure-and-performance/