B*Tree 인덱스 - 편집 역사

Dbstudy: /* BTree 인덱스 작동 방식을 파이썬으로 구현 /

2025-09-22T05:03:21Z

B*Tree 인덱스 작동 방식을 파이썬으로 구현

← 이전 판		2025년 9월 22일 (월) 14:03 판
52번째 줄:		52번째 줄:

	💻 파이썬으로 B-Tree 인덱스 구현하기		💻 파이썬으로 B-Tree 인덱스 구현하기
	아래 코드는 BTree 클래스를 중심으로 Node 클래스를 사용하여 B-tree의 핵심 기능을 구현합니다. 이 예제에서는 노드당 최대 3개의 키를 가질 수 있는 2-3-4 B-tree를 기반으로 합니다.
	1. 노드 클래스 (Node)		* 아래 코드는 BTree 클래스를 중심으로 Node 클래스를 사용하여 B-tree의 핵심 기능을 구현합니다.
	각 노드의 정보를 담는 클래스입니다.		* 이 예제에서는 노드당 최대 3개의 키를 가질 수 있는 2-3-4 B-tree를 기반으로 합니다.

			==== 노드 클래스 (Node)====
			* 각 노드의 정보를 담는 클래스입니다.
			<source lang=python>
	class Node:		class Node:
	def __init__(self, is_leaf=False):		def __init__(self, is_leaf=False):
61번째 줄:		65번째 줄:
	self.is_leaf = is_leaf # 리프 노드인지 여부		self.is_leaf = is_leaf # 리프 노드인지 여부
	self.rowids = [] # 리프 노드에만 있는 실제 데이터의 주소 (예시)		self.rowids = [] # 리프 노드에만 있는 실제 데이터의 주소 (예시)
			</source>

	2. B-Tree 클래스 (BTree)		==== B-Tree 클래스 (BTree) ====
	실제 B-tree의 동작을 담당하는 클래스입니다. 삽입, 탐색, 노드 분할 등의 로직을 포함합니다.		* 실제 B-tree의 동작을 담당하는 클래스입니다. 삽입, 탐색, 노드 분할 등의 로직을 포함합니다.
			<source lang=python>
	class BTree:		class BTree:
	def __init__(self, t):		def __init__(self, t):
159번째 줄:		165번째 줄:
	for child in node.children:		for child in node.children:
	self.print_tree(child, level + 1)		self.print_tree(child, level + 1)
			</source>

	3. 사용 예제		==== 사용 예제 ====
	위에서 만든 B-tree 클래스를 사용하여 인덱스를 구축하고 탐색하는 과정을 시뮬레이션해봅니다.		* 위에서 만든 B-tree 클래스를 사용하여 인덱스를 구축하고 탐색하는 과정을 시뮬레이션해봅니다.
			<source lang=python>
	if __name__ == "__main__":		if __name__ == "__main__":
	b_tree = BTree(t=2) # 2-3 B-tree (노드당 최대 3개 키)		b_tree = BTree(t=2) # 2-3 B-tree (노드당 최대 3개 키)
195번째 줄:		203번째 줄:
	# 키 6에 대한 ROWID: rowid_3		# 키 6에 대한 ROWID: rowid_3
	# 키 25에 대한 ROWID: None		# 키 25에 대한 ROWID: None
			</source>

	📝 코드 해설		📝 코드 해설
	* BTree(t=2): t는 B-tree의 최소 차수(minimum degree)를 의미합니다. t=2는 노드당 최소 1개, 최대 3개의 키를 가질 수 있음을 뜻합니다. 오라클의 실제 B-tree는 훨씬 높은 차수를 사용해 노드당 더 많은 키를 저장합니다.
	* insert(key, rowid): 새로운 키를 트리에 삽입하는 메서드입니다. 루트 노드가 가득 찼을 때 트리의 높이를 증가시키기 위해 루트 노드를 분할하는 로직이 포함되어 있습니다.		* BTree(t=2): t는 B-tree의 최소 차수(minimum degree)를 의미합니다.
	* _insert_non_full(node, key, rowid): 재귀적으로 적절한 위치를 찾아 키를 삽입하는 내부 메서드입니다. 삽입하려는 노드가 리프 노드인지, 아니면 브랜치 노드인지에 따라 다른 로직을 수행합니다.		** t=2는 노드당 최소 1개, 최대 3개의 키를 가질 수 있음을 뜻합니다.
	* _split_child(parent_node, i): B-tree의 핵심적인 동작 중 하나로, 노드가 가득 찼을 때 중간 키를 부모 노드로 올리고 두 개의 자식 노드로 분할하는 로직을 구현합니다. 이 과정을 통해 트리의 균형이 유지됩니다.		** 오라클의 실제 B-tree는 훨씬 높은 차수를 사용해 노드당 더 많은 키를 저장합니다.
	* search(key): 주어진 키를 트리를 따라 내려가며 찾는 메서드입니다. 키를 찾으면 해당 ROWID를 반환하고, 찾지 못하면 None을 반환합니다.		* insert(key, rowid): 새로운 키를 트리에 삽입하는 메서드입니다.
			** 루트 노드가 가득 찼을 때 트리의 높이를 증가시키기 위해 루트 노드를 분할하는 로직이 포함되어 있습니다.
			* _insert_non_full(node, key, rowid): 재귀적으로 적절한 위치를 찾아 키를 삽입하는 내부 메서드입니다.
			** 삽입하려는 노드가 리프 노드인지, 아니면 브랜치 노드인지에 따라 다른 로직을 수행합니다.
			* _split_child(parent_node, i): B-tree의 핵심적인 동작 중 하나로, 노드가 가득 찼을 때 중간 키를 부모 노드로 올리고 두 개의 자식 노드로 분할하는 로직을 구현합니다. 이 과정을 통해 트리의 균형이 유지됩니다.
			* search(key): 주어진 키를 트리를 따라 내려가며 찾는 메서드입니다. 키를 찾으면 해당 ROWID를 반환하고, 찾지 못하면 None을 반환합니다.

	이 코드는 오라클 B-tree의 기본 원리를 설명하기 위한 예제이며, 실제 오라클 데이터베이스의 복잡한 인덱스 관리, 동시성 제어, 트랜잭션 처리와 같은 기능은 포함하고 있지 않습니다.		이 코드는 오라클 B-tree의 기본 원리를 설명하기 위한 예제이며, 실제 오라클 데이터베이스의 복잡한 인덱스 관리, 동시성 제어, 트랜잭션 처리와 같은 기능은 포함하고 있지 않습니다.

			[[category:oracle]]

Dbstudy: /* BTree 인덱스 단점 /

2025-09-22T04:59:28Z

B*Tree 인덱스 단점

← 이전 판		2025년 9월 22일 (월) 13:59 판
41번째 줄:		41번째 줄:

	=== B*Tree 인덱스 단점 ===		=== B*Tree 인덱스 단점 ===
	#분포도(Cardinality)가 낮은 ~~컬럼의~~ 경우 B*TREE 인덱스가 불리함		# 분포도(Cardinality)가 낮은 컬럼(예 남,여 구분(M,F) 이나 사용여부(Y,N) 같은)의 경우 B*TREE 인덱스가 불리함
	#OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함		# OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함
	#인덱스 연산 불가		# 인덱스 연산 불가
	#인덱스 확장 시 부하 발생		# 인덱스 확장 시 부하 발생
	----		----

Dbstudy: /* B+Tree 인덱스 단점 */

2025-09-22T04:57:30Z

B+Tree 인덱스 단점

← 이전 판		2025년 9월 22일 (월) 13:57 판
40번째 줄:		40번째 줄:
	----		----

	=== B+Tree 인덱스 단점 ===		=== B*Tree 인덱스 단점 ===
	#분포도(Cardinality)가 낮은 컬럼의 경우 B*TREE 인덱스가 불리함		#분포도(Cardinality)가 낮은 컬럼의 경우 B*TREE 인덱스가 불리함
	#OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함		#OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함
46번째 줄:		46번째 줄:
	#인덱스 확장 시 부하 발생		#인덱스 확장 시 부하 발생
	----		----

	===B*Tree 인덱스 작동 방식을 파이썬으로 구현===		===B*Tree 인덱스 작동 방식을 파이썬으로 구현===
	*오라클 B-tree 인덱스의 구조를 핵심적인 개념을 담은 간소화된 예제입니다.		*오라클 B-tree 인덱스의 구조를 핵심적인 개념을 담은 간소화된 예제입니다.

Dbstudy: /* B+Tree 인덱스 장점 */

2025-09-22T04:57:18Z

B+Tree 인덱스 장점

← 이전 판		2025년 9월 22일 (월) 13:57 판
34번째 줄:		34번째 줄:


	=== B+Tree 인덱스 장점 ===		=== B*Tree 인덱스 장점 ===
	# 인덱스를 이용해 데이터에 엑세스할 때 모든 인덱스 엔트리에 대해 균형(Balance)을 맞춤		# 인덱스를 이용해 데이터에 엑세스할 때 모든 인덱스 엔트리에 대해 균형(Balance)을 맞춤
	#인덱스를 이용한 범위(Range) 스캔 시 Double Linked List를 사용하기 때문에 다른 인덱스보다 더 유리하며 ACESENDING과 DESCENDING도 가능함		#인덱스를 이용한 범위(Range) 스캔 시 Double Linked List를 사용하기 때문에 다른 인덱스보다 더 유리하며 ACESENDING과 DESCENDING도 가능함

Dbstudy: /* 데이터 삭제시 작동 방식 */

2025-09-22T04:57:03Z

데이터 삭제시 작동 방식

← 이전 판		2025년 9월 22일 (월) 13:57 판
20번째 줄:		20번째 줄:
	====데이터 삭제시 작동 방식====		====데이터 삭제시 작동 방식====
	*데이터입력시 발생되는 작동방식과 정반대의 작업을 수행한다.		*데이터입력시 발생되는 작동방식과 정반대의 작업을 수행한다.
	#데이터가 삭제되면 해당 인덱스 엔트리의 연결이 끊어진다.		#데이터가 삭제되면 해당 인덱스 엔트리의 연결이 끊어진다.그렇게 함으로써 루트 블록으로부터 해당 인덱스 엔트리를 인식하지 못하게 한다.
	#: 그렇게 함으로써 루트 블록으로부터 해당 인덱스 엔트리를 인식하지 못하게 한다.
	#삭제된 인덱스 엔트리의 공간은 추가를 위해 공간 해제를 수행하게 되며, 리프 블록에 하나의 인덱스 엔트리라도 남게 되면 인덱스 리프 블록은 유지되게 된다.		#삭제된 인덱스 엔트리의 공간은 추가를 위해 공간 해제를 수행하게 되며, 리프 블록에 하나의 인덱스 엔트리라도 남게 되면 인덱스 리프 블록은 유지되게 된다.
	#많은 인덱스 엔트리가 삭제되면 삭제된 공간은 반납된다.		#많은 인덱스 엔트리가 삭제되면 삭제된 공간은 반납된다.그러나 해당 리프 블록의 전체 데이터가 삭제되지 않는 한 해당 리프 블록은 반납되지 않는다.
	#그러나 해당 리프 블록의 전체 데이터가 삭제되지 않는 한 해당 리프 블록은 반납되지 않는다.
	#해당 리프 블록에 새로운 인덱스 엔트리가 추가로 저장되지 않는다면 공간이 낭비되게 된다.		#해당 리프 블록에 새로운 인덱스 엔트리가 추가로 저장되지 않는다면 공간이 낭비되게 된다.

2025년 9월 22일 (월) 04:55에 Dbstudy님의 편집

2025-09-22T04:55:17Z

← 이전 판		2025년 9월 22일 (월) 13:55 판
9번째 줄:		9번째 줄:
	:::# 리프(Leaf) 노드: 트리의 가장 아래에 위치하며, 인덱스 키와 해당 데이터가 저장된 ROWID(실제 데이터의 물리적 주소)를 포함합니다. 리프 노드는 서로 양방향으로 연결되어 있어 인덱스 범위를 순차적으로 스캔하는 데 유리합니다.		:::# 리프(Leaf) 노드: 트리의 가장 아래에 위치하며, 인덱스 키와 해당 데이터가 저장된 ROWID(실제 데이터의 물리적 주소)를 포함합니다. 리프 노드는 서로 양방향으로 연결되어 있어 인덱스 범위를 순차적으로 스캔하는 데 유리합니다.
	:::# 페이지(Page): B*tree의 각 노드는 물리적으로 페이지 또는 블록이라 불리는 단위에 저장됩니다.		:::# 페이지(Page): B*tree의 각 노드는 물리적으로 페이지 또는 블록이라 불리는 단위에 저장됩니다.
			https://velog.velcdn.com/images%2Fanrun%2Fpost%2F37dbe75c-ca7a-447b-914b-448952d40470%2Fbtree.jpeg
	}}		}}

	===인덱스 작동 방식===		===인덱스 작동 방식===
	===데이터 추가시 작동 방식===		====데이터 추가시 작동 방식====
	#테이블에 데이터가 입력되면 해당 테이블에 존재하는 인덱스에도 추가된 데이터의 인덱스 엔트리가 추가된다.		#테이블에 데이터가 입력되면 해당 테이블에 존재하는 인덱스에도 추가된 데이터의 인덱스 엔트리가 추가된다.
	# 테이블에 추가되는 데이터의 인덱스 키(Key) 값의 저장 위치를 찾기 위해 인덱스 리프 블록을 확인해 찾는다.		# 테이블에 추가되는 데이터의 인덱스 키(Key) 값의 저장 위치를 찾기 위해 인덱스 리프 블록을 확인해 찾는다.
18번째 줄:		18번째 줄:
	#해당 인덱스 블록에 여유 공간이 없을 경우, 해당 블록은 2개의 인덱스 리프 블록으로 분기돼 인덱스 키들은 다시 정렬하고 분기된 2개의 인덱스 리프 블록을 통해 추가된다. 이 때 리프 블록을 연결하고 있는 브랜치 블록과 루트 블록의 정보가 갱신될 수 있다.		#해당 인덱스 블록에 여유 공간이 없을 경우, 해당 블록은 2개의 인덱스 리프 블록으로 분기돼 인덱스 키들은 다시 정렬하고 분기된 2개의 인덱스 리프 블록을 통해 추가된다. 이 때 리프 블록을 연결하고 있는 브랜치 블록과 루트 블록의 정보가 갱신될 수 있다.

	===데이터 삭제시 작동 방식===		====데이터 삭제시 작동 방식====
	*데이터입력시 발생되는 작동방식과 정반대의 작업을 수행한다.		*데이터입력시 발생되는 작동방식과 정반대의 작업을 수행한다.
	#데이터가 삭제되면 해당 인덱스 엔트리의 연결이 끊어진다.		#데이터가 삭제되면 해당 인덱스 엔트리의 연결이 끊어진다.
27번째 줄:		27번째 줄:
	#해당 리프 블록에 새로운 인덱스 엔트리가 추가로 저장되지 않는다면 공간이 낭비되게 된다.		#해당 리프 블록에 새로운 인덱스 엔트리가 추가로 저장되지 않는다면 공간이 낭비되게 된다.

	===갱신 Update Operation===		====갱신 Update Operation====
	#삭제와 추가 작업이 동시에 수행되는 작업이다.		#삭제와 추가 작업이 동시에 수행되는 작업이다.
	#테이블에 데이터가 순차적으로 증가해 추가되는 경우 인덱스의 우측으로 인덱스 엔트리가 집중돼 B*TREE의 가장 중요한 특징인 균형(Balance)이 무너지게 된다.		#테이블에 데이터가 순차적으로 증가해 추가되는 경우 인덱스의 우측으로 인덱스 엔트리가 집중돼 B*TREE의 가장 중요한 특징인 균형(Balance)이 무너지게 된다.
34번째 줄:		34번째 줄:
	----		----

	~~==인덱스 구조==~~

	~~https://velog.velcdn.com/images%2Fanrun%2Fpost%2F37dbe75c-ca7a-447b-914b-448952d40470%2Fbtree.jpeg~~

	~~#B*tree는 leaf node 와 non-leaf 로 구성~~
	~~#leaf node 부터 root node 까지의 길이는 모든 리프가 동일하다는 특징을 가지고 있다.~~
	~~#:즉, 모든 리프 노드의 레벨은 동일하다.~~
	~~#leaf node 간에는 링크드 리스트(linked list)로 연결되어 있어 여러 값을 스캔할 때 유리하다.~~
	~~# leaf node 는 정방향(Ascending)과 역방향(Descending) 스캔이 둘 다 가능하도록 양방향 연결 리스트(Double linked list) 구조로 연결돼 있다.~~
	~~----~~

	===B+Tree 인덱스 장점===		=== B+Tree 인덱스 장점 ===
	# 인덱스를 이용해 데이터에 엑세스할 때 모든 인덱스 엔트리에 대해 균형(Balance)을 맞춤		# 인덱스를 이용해 데이터에 엑세스할 때 모든 인덱스 엔트리에 대해 균형(Balance)을 맞춤
	#인덱스를 이용한 범위(Range) 스캔 시 Double Linked List를 사용하기 때문에 다른 인덱스보다 더 유리하며 ACESENDING과 DESCENDING도 가능함		#인덱스를 이용한 범위(Range) 스캔 시 Double Linked List를 사용하기 때문에 다른 인덱스보다 더 유리하며 ACESENDING과 DESCENDING도 가능함
51번째 줄:		42번째 줄:
	----		----

	===B+Tree 인덱스 단점===		=== B+Tree 인덱스 단점 ===
	#분포도(Cardinality)가 낮은 컬럼의 경우 B*TREE 인덱스가 불리함		#분포도(Cardinality)가 낮은 컬럼의 경우 B*TREE 인덱스가 불리함
	#OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함		#OR 연산자에 대해 테이블 전체를 스캔(Full Scan)하는 것은 위험함

Dbstudy: /* 데이터 추가시 작동 방식 */

2025-09-22T04:52:04Z

데이터 추가시 작동 방식

← 이전 판		2025년 9월 22일 (월) 13:52 판
16번째 줄:		16번째 줄:
	# 테이블에 추가되는 데이터의 인덱스 키(Key) 값의 저장 위치를 찾기 위해 인덱스 리프 블록을 확인해 찾는다.		# 테이블에 추가되는 데이터의 인덱스 키(Key) 값의 저장 위치를 찾기 위해 인덱스 리프 블록을 확인해 찾는다.
	#인덱스 블록의 여유 공간에 해당 인덱스 엔트리를 추가한다.		#인덱스 블록의 여유 공간에 해당 인덱스 엔트리를 추가한다.
	#해당 인덱스 블록에 여유 공간이 없을 경우, 해당 블록은 2개의 인덱스 리프 블록으로 분기돼 인덱스 키들은 다시 정렬하고		#해당 인덱스 블록에 여유 공간이 없을 경우, 해당 블록은 2개의 인덱스 리프 블록으로 분기돼 인덱스 키들은 다시 정렬하고 분기된 2개의 인덱스 리프 블록을 통해 추가된다. 이 때 리프 블록을 연결하고 있는 브랜치 블록과 루트 블록의 정보가 갱신될 수 있다.
	#:분기된 2개의 인덱스 리프 블록을 통해 추가된다. 이 때 리프 블록을 연결하고 있는 브랜치 블록과 루트 블록의 정보가 갱신될 수 있다.

	===데이터 삭제시 작동 방식===		===데이터 삭제시 작동 방식===

Dbstudy: /* BTree 인덱스 /

2025-09-22T04:51:41Z

B*Tree 인덱스

← 이전 판		2025년 9월 22일 (월) 13:51 판
7번째 줄:		7번째 줄:
	:::# 루트(Root) 노드: 트리의 최상위 노드.		:::# 루트(Root) 노드: 트리의 최상위 노드.
	:::# 브랜치(Branch) 노드: 루트와 리프 노드 사이에 위치하며, 자식 노드를 가리키는 포인터를 포함합니다.		:::# 브랜치(Branch) 노드: 루트와 리프 노드 사이에 위치하며, 자식 노드를 가리키는 포인터를 포함합니다.
	:::# 리프(Leaf) 노드: 트리의 가장 아래에 위치하며, 인덱스 키와 해당 데이터가 저장된 ROWID(실제 데이터의 물리적 주소)를 포함합니다.		:::# 리프(Leaf) 노드: 트리의 가장 아래에 위치하며, 인덱스 키와 해당 데이터가 저장된 ROWID(실제 데이터의 물리적 주소)를 포함합니다. 리프 노드는 서로 양방향으로 연결되어 있어 인덱스 범위를 순차적으로 스캔하는 데 유리합니다.
	~~:::#:~~ 리프 노드는 서로 양방향으로 연결되어 있어 인덱스 범위를 순차적으로 스캔하는 데 유리합니다.
	:::# 페이지(Page): B*tree의 각 노드는 물리적으로 페이지 또는 블록이라 불리는 단위에 저장됩니다.		:::# 페이지(Page): B*tree의 각 노드는 물리적으로 페이지 또는 블록이라 불리는 단위에 저장됩니다.
	}}		}}

Dbstudy: /* BTree 인덱스 /

2025-09-22T04:41:29Z

B*Tree 인덱스

← 이전 판		2025년 9월 22일 (월) 13:41 판
3번째 줄:		3번째 줄:
	{{틀:핵심		{{틀:핵심
	\|제목='''<big>대용량 데이터를 효율적으로 검색, 삽입, 삭제하기 위해 사용하는 자가 균형 이진 탐색 트리</big>'''		\|제목='''<big>대용량 데이터를 효율적으로 검색, 삽입, 삭제하기 위해 사용하는 자가 균형 이진 탐색 트리</big>'''
	* '''(중요) 어떤 노드에서든 리프 노드까지의 거리가 항상 일정하게 유지되어 탐색 시간이 일정함.(3D 입체적 탐색)'''		:::* '''(중요) 어떤 노드에서든 리프 노드까지의 거리가 항상 일정하게 유지되어 탐색 시간이 일정함.(3D 입체적 탐색)'''
	\|내용='''<big>오라클 B*tree 인덱스의 특징</big>'''		\|내용='''<big>오라클 B*tree 인덱스의 특징</big>'''
	:::# 루트(Root) 노드: 트리의 최상위 노드.		:::# 루트(Root) 노드: 트리의 최상위 노드.

Dbstudy: /* BTree 인덱스 /

2025-09-22T04:41:10Z

B*Tree 인덱스

← 이전 판		2025년 9월 22일 (월) 13:41 판
3번째 줄:		3번째 줄:
	{{틀:핵심		{{틀:핵심
	\|제목='''<big>대용량 데이터를 효율적으로 검색, 삽입, 삭제하기 위해 사용하는 자가 균형 이진 탐색 트리</big>'''		\|제목='''<big>대용량 데이터를 효율적으로 검색, 삽입, 삭제하기 위해 사용하는 자가 균형 이진 탐색 트리</big>'''
	* '''~~<big>~~(중요) 어떤 노드에서든 리프 노드까지의 거리가 항상 일정하게 유지되어 탐색 시간이 일정함.(3D 입체적 탐색)~~</big>~~'''		* '''(중요) 어떤 노드에서든 리프 노드까지의 거리가 항상 일정하게 유지되어 탐색 시간이 일정함.(3D 입체적 탐색)'''
	\|내용='''<big>오라클 B*tree 인덱스의 특징</big>'''		\|내용='''<big>오라클 B*tree 인덱스의 특징</big>'''
	:::# 루트(Root) 노드: 트리의 최상위 노드.		:::# 루트(Root) 노드: 트리의 최상위 노드.

B*Tree 인덱스 - 편집 역사

Dbstudy: /* B*Tree 인덱스 작동 방식을 파이썬으로 구현 */

Dbstudy: /* B*Tree 인덱스 단점 */

Dbstudy: /* B+Tree 인덱스 단점 */

Dbstudy: /* B+Tree 인덱스 장점 */

Dbstudy: /* 데이터 삭제시 작동 방식 */

2025년 9월 22일 (월) 04:55에 Dbstudy님의 편집

Dbstudy: /* 데이터 추가시 작동 방식 */

Dbstudy: /* B*Tree 인덱스 */

Dbstudy: /* B*Tree 인덱스 */

Dbstudy: /* B*Tree 인덱스 */

Dbstudy: /* BTree 인덱스 작동 방식을 파이썬으로 구현 /

Dbstudy: /* BTree 인덱스 단점 /

Dbstudy: /* BTree 인덱스 /

Dbstudy: /* BTree 인덱스 /

Dbstudy: /* BTree 인덱스 /