B+Tree에 대해 가장 기본적인 강의영상
오늘 하루가 B+가 아니라 A+가 되라는 유머까지 겸비하셨다
https://www.youtube.com/watch?v=2q9UYVLSNeI&ab_channel=AppleJuiceTeaching
일단 BST가 뭘까
https://algorithm90.tistory.com/27
BST는 파이썬의 list와 linked list 둘의 단점을 모두 보완할 수 있습니다.
list는 오프셋을 통한 인덱싱 기능으로 list 안을 search 할 때 O(1)의 시간 복잡도를 갖지만 insert나 delete 할 때 맨 뒤에 값을 더하거나 빼는 상황이 아니라면 최악의 경우 list 내의 모든 요소를 한 칸씩 이동시켜야 하는 상황이 생겨 O(n)의 시간 복잡도를 갖는 단점이 있습니다.
linked list는 반대로 insert와 delete 할 때 해당 노드와 앞 뒤 노드를 연결시키거나 끊는 방법으로 빠르게 처리 가능하지만 search 할 때 최악의 경우 header부터 끝까지 이동해야 할 수 있으므로 O(n)의 시간복잡도를 갖게 됩니다.
search나 insert/delete 한쪽만을 사용해서 기능을 구현하는 경우는 적은데, BST search와 insert, delete 기능의 빅 O가 모두 O(logN)이라는 점에서 이점이 있습니다.
B-tree는 각 Node가 Splitter 역할을 하면서 값을 나타낸다면,
B+tree는 leaf Node에 있는 것들만이 실제 값이고, 나머지는 Splitter이다. B+tree의 경우, 모든 값들이 Leaf Node에 존재한다. 같은 level에 존재하기 때문에, Range를 통해 값들의 범위를 구하기 용이하다.
B-Tree
B-Tree Visualization
https://www.cs.usfca.edu/~galles/visualization/BTree.html
B-Tree의 각 노드는 가질 수 있는 숫자의 최소/최대 갯수가 정해져있다. (단, Root Node만은 1개만 가지고 있을 수 있다)
B-트리의 노드는 대개 항목과 자식 포인터의 순서 집합으로 표현된다. 루트 노드를 제외한 모든 노드는 임의의 수 L, U(L<U)에 대해 최소 L 항목, 최대 U 항목을 가지고 있으며, 최대 U+1개의 자식 포인터를 가지고 있다. 모든 내부 노드에서, 자식 포인터의 수는 언제나 항목 개수보다 하나가 많다. 모든 리프 노드가 동일한 높이에 있기 때문에, 노드는 일반적으로 리프 노드인지 내부 노드인지 판별하는 수단을 가질 이유가 없다.
B-Tree Deletion
삭제가 복잡하다. 잘 알아두자.
https://www.youtube.com/watch?v=GKa_t7fF8o0&ab_channel=Jenny%27slecturesCS%2FITNET%26JRF
B+Tree
B+Tree Visualization
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
Database에서 사용하기 좋다. B+Tree는 Range Queries 를 처리하기 좋은데, Database에서 이러한 일이 많이 일어나기 때문이다.
Eeah nodes has a threshhold.
각 노드는 한계점을 가지고 있다. 2개, 3개 등등
캡쳐
