Searching
Contents
Trees
-
Tree Terminology
Terminology |
Explain |
Example |
Root |
node without parent |
A |
Child |
if node u is the parent of node v, v is a child of u |
A |
Internal node |
node with at least one child |
A, B, C, F |
External node (=Leaf) |
node without children |
E, I, J, K, G, H, D |
Ancestors of a node |
parent, grandparent, great-grandparent, etc. |
ย |
Siblings of a node |
Any node which shares a parent |
ย |
Depth of a node |
number of ancestors (๋
ธ๋์ ์์ฑ) |
K์ ๊ฒฝ์ฐ, A, B, F์ด๋ฏ๋ก 3 |
Height of a tree |
maximum depth of any node (ํธ๋ฆฌ์ ์์ฑ) |
3 |
Descendant of a node |
child, grandchild, great-grandchild, etc. |
ย |
Subtree |
tree consisting of a node and its descendants (๋ถ๋ถ์งํฉ ๊ฐ์ ๊ฐ๋
) |
ย |
Degree |
number of children of a node (ํธ๋ฆฌ์ ์์ฑ) |
F์ ๊ฒฝ์ฐ, I, J, K์ด๋ฏ๋ก 3 |
Edge |
a pair of node (u, v) such that u is a parent of v((C, H)) |
ย |
Path |
A sequence of nodes such that any two consecutive nodes form an edge |
A, B, F, J |
Ordered tree |
a tree with a linear ordering defined for the children of each node |
ย |
1) Preorder Traversal (P-L-R)
- A traversal visits the nodes of a tree in a systematic manner
- search ๋์ ๋ค๋ฅด๋ค. (๋ชจ๋ node๋ค์ ์ฐพ์๊ฐ๋ ๊ท์น)
- In a preorder traversal, a node is visited before its descendants
- Application: print a structured document
Algorithm preOrder(T,p)
visit(p)
for each child q of p
preOrder(T,q)
2) Postorder Traversal (L-P-R)
- In a post order traversal, a node is visited after its descendants
- Application: compute space used by files in a directory and its subdirectories
Algorithm postOrder(T,p)
for each child q of p
postOrder(T,q)
visit(p)
3) In-order Traversal
- In an inorder traversal, a node is visited after its left subtree and before its right subtree
- Application: draw a binary tree
x(v)
= inorder rank of v
y(v)
= depth of v
Algorithm inOrder(T,p)
if ยฌp.isExternal()
inOrder(T,p.left())
visit(p)
if ยฌp.isExternal()
inOrder(T,p.right())
4) Euler Tour Traversal
- Generic traversal of a binary tree
- Includes as special cases the preorder, postorder and inorder traversals
- Walk around the tree and visit each node three times: (ํ ๋
ธ๋๋ฅผ 3๋ฒ ๋ฐ๋ณต)
- on the left (
preorder
)
- from below (
inorder
)
- on the right (
postorder
)
- ํ๋ถ๊ทธ๋ฆฌ๊ธฐ ๋๋
Algorithm eulerTour(T,p)
visit(p) on the left // preOrder
if ยฌp.isExternal()
eulerTour(T,p.left())
visit(p) from below // inOrder
if ยฌp.isExternal()
eulerTour(T,p.right())
visit(p) on the right // postOrder
์ด์ง ํธ๋ฆฌ (Binary Tree)
- A binary tree is a tree with the following properties:
- Each internal node has at most two children
(exactly two for proper binary trees)
- The children of a node are an ordered pair
- We call the children of an internal node left child and right child
- Are cursive definition
- A binary tree is either empty or consists of:
- A node
r
,called the root of T
and storing an element
- A binary tree, called the left subtree of
T
- A binary tree, called the right subtree of
T
- Applications:
- arithmetic expressions
- decision processes
- searching
Properties of Binary Trees
-
Notation
n
: number of nodes
e
: number of external nodes
i
: number of internal nodes
h
: height
-
Properties
e
= i
+ 1 (์ธ๋ถ๋
ธ๋ ์ = ๋ด๋ถ๋
ธ๋ ์ + 1)
n
= 2e
- 1
h
<= i
h
<= (n
- 1)/2
e
<= 2^h
h
>= log_2(e
)
h
>= log_2(n
+ 1) - 1
Arithmetic Expression Tree
- Binary tree associated with an arithmetic expression
- Internal nodes: operators
- External nodes(leaves): operands
์ด์ง ํ์ ํธ๋ฆฌ (Binary Serarch Tree)
- A binary search tree is a binary tree storing keys (or key-value entries) at its internal nodes and satisfying the following property:
- Let
u
, v
, and w
be three nodes such that u
is in the left subtree of v
and w
is in the right subtree of v
. We have
- key(
u
) <= key(v
) <= key(w
)
- External nodes do not store items
- An inorder traversal of a binary search trees visits the keys in increasing order
Search
- To search for a key
k
, we trace a downward path starting at the root
- The next node visited depends on the comparison of
k
with the key of the current node
- If we reach a leaf, the key is not found and we return a null position
Algorithm TreeSearch(k, u)
if u.isExternal()
return u
if k < u.key()
return TreeSearch(k, u.left())
else if k = u.key()
return u
else // k > u.key()
return TreeSearch(k, u.right())
BST์์์ Insertion
์ฐธ๊ณ : https://new93helloworld.tistory.com/115?category=691027
- Step 1) Find
k
- Step 2) Insert
k
- Example:
- Assume
k
is not already in the tree, and let w
be the leaf reached by the search
- We insert
k
at node w
and expand w
into an internal node
public:
void insertItem(const Key& k, const Element& e) // insert (key, element)
{ inserter(k, e); }
protected:
BTPosition inserter(const Key& k, const Element& e) { // insert utillity
BTPosition p = finder(k, T.root()); // find insertion spot
// ๋ด๋ถ๋
ธ๋์ธ ๊ฒฝ์ฐ
while (T.isInternal(p)) // key already exists?
// look further
p = finder(k, T.rightChild(p)); // leftChild๋ก ํด๋ ์๋ฌด ์๊ด ์์
// ์ธ๋ถ๋
ธ๋์ธ ๊ฒฝ์ฐ
T.expandExternal(p); // add new node here
setItem(p, BSTItem(k, e)); // store (key, element)
return p;
}
Example: Insertion
Removal
์ฐธ๊ณ : https://new93helloworld.tistory.com/116?category=691027
- To perform operation
erase(k)
, we search for key k
- Assume key
k
is in the tree, and let v
be the node storing k
- If node
v
has a leaf child w
, we remove v
and w
from the tree with operation removeAboveExternal(w)
, which removes w
and its parent
- An example operation of
removeAboveExternal(w)
public:
// remove using key
void removeElement(const Key& k) throw(NonexistentElementException) {
BTPosition p = finder(k, T.root()); // find the node
if (p.isNull()) // not found?
throw NonexistentElementException("Remove nonexistent element");
remover(p); // remove it
}
protected:
BTPosition remover(const BTPosition& r) { // remove utility
BTPosition p;
if (T.isExternal(T.leftChild(r))) // left is external?
p = T.leftChild(r); // remove from left
else if (T.isExternal(T.rightChild(r))) // right is external?
p = T.rightChild(r); // remove from right
else {
p = T.rightChild(r); // p = replacement
do
p = T.leftChild(p); // ... right subtree
while (T.isInternal(p));
setItem(r, T.parent(p).element()); // copy parent(p) to r
}
return T.removeAboveExternal(p); // remove p and parent
}
Example: Removal
erase(4)
Removing an entry with key 32
Removal (cont.)
- We consider the case where the key
k
to be removed is stored at a node v
whose children are both internal
- we find the internal node
w
that follows v
in an inorder traversal
- we copy
key(w)
into node v
- we remove node
w
and its left child z
(which must be a leaf) by means of operation removeAboveExternal(z)
Example: Removal
erase(3)
Removing an entry with key 65
- The height
h
is O(n)
in the worst case
- Consider an ordered map with
n
items implemented by means of a binary search tree of height h
- Functions
find
, put
and erase
take O(h) = O(n)
time
- Functions
size
, empty
take O(1)
๊ท ํ ํธ๋ฆฌ (Balanced Tree)
- Balanced์ ์ ์ : ๋ชจ๋ leaf node๋ค์ด ๊ฐ์ level์ ์๋ ์ํ
- Balanced Tree์ ์ ์ : ์์์ ๋
ธ๋์์ ํ์๋๋ ์ข์ฐ์ ๋ถ๋ถํธ๋ฆฌ์ ๋
ธ๋ ์๊ฐ ์ต๋ 1 ๋ฐ์ ํ๋ฆฌ์ง ์๋ ํธ๋ฆฌ
- ์ด์ง ํธ๋ฆฌ ์๊ณ ๋ฆฌ์ฆ
- ์ต์
์ ๊ฒฝ์ฐ ์ฑ๋ฅ์ด ๋์จ
- ์ ๋ ฌ๋ ํ์ผ ๋๋ ์ญ์์ผ๋ก ์ ๋ ฌ๋ ํ์ผ, ํฐ ํค์ ์์ ํค๊ฐ ๊ต๋๋ก ๋์ค๋ ํ์ผ
- ์ฑ๋ฅ ๊ฐ์
- ํต ์ ๋ ฌ์ ๊ฒฝ์ฐ ์ฑ๋ฅ ๊ฐ์ ๋ฐฉ๋ฒ์ ํ๋ฅ ์ ์ํด ์์์ ๋ถํ ์์๋ฅผ ์ ํํ๋ ์ ๋ฐ์ ์์
- ์ด์ง ํธ๋ฆฌ ํ์์ ๊ฒฝ์ฐ์๋ ํธ๋ฆฌ๋ฅผ ๊ท ํ ์๊ฒ ์ ์งํ๋ฉด ์ต์
์ ์ํฉ์ ํผํ ์ ์์
- ์ผ๋ฐ์ ์ธ ๊ฐ๋
์ ์ฝ๊ฒ ๊ธฐ์ ํ ์ ์์ง๋ง, ์ค์ ๊ตฌํ์์๋ ํน์ํ ์ํฉ์ ๊ณ ๋ คํด์ผ ํจ
2-4 Tree
Red-Black Tree
A red-black tree is a representation of a (2,4) tree by means of a binary tree whose nodes are colored red or black
Hashing
- ๋ชจ๋ ํค์ ๋ ์ฝ๋๋ฅผ ์ฐ์ ์ฐ์ฐ์ ์ํด ํ ๋ฒ์ ๋ฐ๋ก ์ ๊ทผํ ์ ์๋ ๊ธฐ๋ฒ
- ํด์ฑ์ ๋จ๊ณ
- ํด์ ํจ์(hash function)๋ฅผ ํตํด ํ์ ํค๋ฅผ ํด์ ํ
์ด๋ธ ์ฃผ์๋ก ๋ณํ
- ๊ฐ์ ํ
์ด๋ธ ์ฃผ์๋ก ์ฌ์๋์์ ๊ฒฝ์ฐ์๋ ์ถฉ๋์ ํด๊ฒฐ(collision-resolution)ํด์ผ ํจ
ํน์ง
- ์๊ฐ๊ณผ ๊ณต๊ฐ์ ๊ท ํ
- ๋ฉ๋ชจ๋ฆฌ์ ์ ํ์ด ์์ ๊ฒฝ์ฐ : ํค๋ฅผ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ก ์ฌ์ฉํ๋ฉด ์ด๋ค ํ์์ด๋ ์ง ํ ๋ฒ์ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ์ผ๋ก ์ํ ๊ฐ๋ฅ
- ์๊ฐ์ ์ ํ์ด ์์ ๊ฒฝ์ฐ : ์ต์ํ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ณ ์์ฐจ ํ์
- ํด์ฑ์ ์ด๋ฌํ ๋ ๊ทน๋จ ์ฌ์ด์์ ํฉ๋ฆฌ์ ์ธ ๊ท ํ์ ์ด๋ฃฐ ์ ์๋ ๋ฐฉ๋ฒ์ ์ ๊ณต
- ํด์ฑ์ ์ฌ์ฉํ๋ ๋ชฉ์ ์ ๊ฐ์ฉํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํจ๊ณผ์ ์ผ๋ก ์ฌ์ฉํ๋ฉด์ ๋น ๋ฅด๊ฒ ๋ฉ๋ชจ๋ฆฌ์ ์ ๊ทผํ๊ธฐ ์ํจ
ํด์ฑ๊ณผ ์ด์ง ํธ๋ฆฌ
- ์ด์ง ํธ๋ฆฌ๋ณด๋ค ํด์ฑ์ ๋ง์ด ์ฌ์ฉํ๋ ์ด์
- ๊ฐ๋จํจ
- ์์ฃผ ๋น ๋ฅธ ํ์ ์๊ฐ
- ์ด์ง ํธ๋ฆฌ์ ์ฅ์
- ๋์
- ์ฝ์
ํ์๋ฅผ ๋ฏธ๋ฆฌ ์๊ณ ์์ง ์์๋ ๋จ
- ์ต์
์ ๊ฒฝ์ฐ ์ฑ๋ฅ์ ๋ณด์ฅ
- ํด์ฑ์ ๊ฒฝ์ฐ ์๋ฌด๋ฆฌ ์ข์ ํด์ํจ์๋ผ๋ ๋ชจ๋ ๊ฐ์ ๊ฐ์ ์ฅ์๋ก ํด์ฑํ๋ ๊ฒฝ์ฐ๊ฐ ๋ฐ์
- ์ฌ์ฉํ ์ ์๋ ์ฐ์ฐ์ ์ข
๋ฅ๊ฐ ๋ง์ (์: ์ ๋ ฌ์ฐ์ฐ)
์ฐ์๋ฒ (chaining)
- ๋์ผ ์ฃผ์๋ก ํด์๋๋ ๋ชจ๋ ์์๊ฐ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ํํ๋ก ์ฐ๊ฒฐ๋จ
- ์ฅ์
- ์์์ ์ญ์ ๊ฐ ์ฉ์ด
- ๋จ์
- ํฌ์ธํฐ ์ ์ฅ์ ์ํ ๊ธฐ์ต๊ณต๊ฐ์ด ํ์
- ๊ธฐ์ต์ฅ์ ํ ๋น์ด ๋์ ์ผ๋ก ์ด๋ฃจ์ด์ ธ์ผ ํจ
์ ํ ํ์ฌ๋ฒ (linear probing)
- ํด์ ํจ์
- ๊ฐ๋ฐฉ ์ฃผ์๋ฒ(open addressing) ์ฌ์ฉ : m ๊ฐ์ด ์
๋ ฅ ์์์ ์๋ณด๋ค ์ปค์ผ ํจ
- ํด๋ฌ์คํฐ๋ง์ด ๋ฐ์
- ์ ์ ๋ ์์น๊ฐ ์ฐ์์ ์ผ๋ก ๋ํ๋๋ ๋ญ์น๊ฐ ์์ผ๋ฉด ์ด๊ฒ์ด ์ ์ ๋ ์ปค์ง๋ ํ์ - ์ด๋ฌํ ๋ญ์น๋ ํ๊ท ํ์ ์๊ฐ์ ์ฆ๊ฐ์ํด
- ์ฑ๋ฅ ํน์ฑ
- ํด์ ํ
์ด๋ธ์ด 2/3 ์ ๋ ์ฐจ ์์ ๊ฒฝ์ฐ, ์ ํ ํ์ฌ๋ฒ์ ํ๊ท ์ ์ผ๋ก 5๋ฒ๋ณด๋ค ์ ์ ํ ์ฌ๋ฅผ ์ํ
- ์ฑ๊ณต์ ์ธ ํ์์ ํ
์ด๋ธ์ด 90% ์ ๋ ์ฐฐ ๋๊น์ง 5๋ฒ ์ดํ์ ํ์ฌ๋ก ๊ฐ๋ฅ
- ์ฑ๊ณต์ ์ด์ง ์์ ํ์์ ํญ์ ์ฑ๊ณต์ ์ธ ํ์์ ๋นํด ๋น์ฉ์ด ๋ง์ด ๋ฌ
์ด์ค ํด์ฑ (double hashing)
Grid File (๋ค์ฐจ์ Hashing)
- ๊ฒฉ์ ํ์ผ
- ์ ์ฒด ๊ณต๊ฐ์ ํ๋ ์ด์์ ๊ฒฉ์(grid)๋ก ๋ถํ
- ๋ฐ์ดํฐ ์ถ๊ฐ์ ๋ฐ๋ผ ๊ธฐ์กด ๊ฒฉ์๋ฅผ ๋ถํ ํ์ฌ ์๋ก์ด ๊ฒฉ์ ๊ตฌ์ฑ
- ํน์ง
- ๋์คํฌ ๊ธฐ๋ฐ -> ๋์ฉ๋ ๋ฐ์ดํฐ ์ฒ๋ฆฌ ๊ฐ๋ฅ
- ํด์ ๊ธฐ๋ฐ -> ์ผ๋ฐ์ ์ผ๋ก ๋ ๋ฒ์ ๋์คํฌ ์ ๊ทผ์ผ๋ก ๋ฐ์ดํฐ ๊ฒ์
- ๊ฒฉ์ ๋ธ๋ก๊ณผ ๋ฐ์ดํฐ ํ์ด์ง
- ๊ธฐ๋ณธ์ ์ผ๋ก ํ๋์ ๊ฒฉ์ ๋ธ๋ก๋น ํ๋์ ๋ฐ์ดํฐ ํ์ด์ง
- ๋ ๊ฐ ์ด์์ ๊ฒฉ์ ๋ธ๋ก์ด ํ๋์ ๋ฐ์ดํฐ ํ์ด์ง์ ๋ํ ๊ณต์ ๊ฐ๋ฅ
๊ธฐ์ ํ์ (Radix searching)
- ํ์ ํค์ ๋์งํธ ์ฑ์ง(0๊ณผ 1)์ ์ด์ฉํด ํ์์ ์ํ ์ด์ง ํธ๋ฆฌ๋ฅผ ๋ง๋ค์ด ํ์์ ์งํ
- ํ์ ํค์ ํด๋น ๋นํธ๊ฐ 0์ด๋ฉด ์ผ์ชฝ ์์์ ๋ฐฉ๋ฌธํ๊ณ , 1์ด๋ฉด ์ค๋ฅธ์ชฝ ์์์ ๋ฐฉ๋ฌธ
- ํ์ ํค๊ฐ ํด ๋๋ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ํ์ ํค๋ฅผ ๋น๊ตํ๋ ๊ฒ์ด ์ฑ๋ฅ์ ๋ง์ ์ํฅ์ ์ค
- ๊ธฐ์ ํ์ ์๊ณ ๋ฆฌ์ฆ์ ํ์ ํค์ ๋น๊ต ํ์๋ฅผ ์ค์ด๋ฉด์ ๊ธฐ์ต ์ฅ์์ ๋ญ๋น๋ฅผ ์ค์ด๊ณ ๊ตฌํ์ ์ฝ ๊ฒ ํ๋ ๋ฐฉํฅ์ผ๋ก ๊ฐ๋ฐ๋์ด ์ด
๋์งํธ ํ์ ํธ๋ฆฌ (Digital Search Tree)
- ํ์ ํค์ ํด๋น ๋นํธ๊ฐ 0์ด๋ฉด ์ผ์ชฝ, 1์ด๋ฉด ์ค๋ฅธ์ชฝ์ผ๋ก ์งํํ์ฌ ๋จ๋ง ๋
ธ๋๊น์ง ์ด๋ฅด๋ฉด ๊ทธ ๊ณณ์ ์๋ก์ด ๋
ธ๋๋ฅผ ์ฝ์
- ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋๋ง๋ค ํ์ ํค๋ฅผ ๋น๊ตํด์ผ ํ๋ฏ๋ก ํ์ ํค๊ฐ ํฐ ๊ฒฝ์ฐ ํค ๋น๊ต์ ๋ง์ ์๊ฐ์ด ๊ฑธ๋ฆผ
- ๊ท ํ์ ๋ง์ง ์์ง๋ง, ์๋๊ฐ ๋น ๋ฅด๋ค.
- ์ฅ์
- ์ดํดํ๊ธฐ ์ฝ๊ณ ๊ตฌํ์ด ๊ฐ๋จํจ
- ๋จ์
- ํ์ ํค์ ๋นํธ์ ๋ฐ๋ผ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ๋ ๋ง๋ค ๋์งํธ ํ์ ํธ๋ฆฌ์ ํค์ ํ์ ํค๋ฅผ ๋งค๋ฒ ๋น๊ตํด์ผํ๋ฏ๋ก, ํ์ ํค๊ฐ ํฐ ๊ฒฝ์ฐ์๋ ํค ๋น๊ต์ ๋ง์ ์๊ฐ์ด ์์
๊ธฐ์ ํ์ ํธ๋ผ์ด (Radix Search Trie)
- ํธ๋ผ์ด(trie) : reTRIEval ์ ์ ์ฉํ๋ค๊ณ ํ์ฌ Fredkin์ด ๋ช
๋ช
ํจ (ํธ๋ฆฌ๋ ์ง์ง ๋๋ฌด, ํธ๋ผ์ด๋ ๋ฉ์ฟจ ๊ฐ์ ๋๋)
- ๋
ธ๋๋ฅผ ๋ด๋ถ ๋
ธ๋์ ์ธ๋ถ ๋
ธ๋๋ก ๋๋์ด ๋ด๋ถ ๋
ธ๋๋ ํ์์ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์ด๋๋ง์ ๋ํ๋ด๊ณ ํค๋ ์ธ๋ถ ๋
ธ๋์๋ง ์ ์ฅ
- ํ์ ๋น ํ ๋ฒ์ ํค ๋น๊ต๋ง์ ์ํํ๋ฏ๋ก ๋น๊ต ์๊ฐ์ ์ ์ฝ
- ๋ด๋ถ ๋
ธ๋๋ ํค๋ฅผ ์ ์ฅํ์ง ์์ผ๋ฏ๋ก ๊ธฐ์ต ์ฅ์์ ๋ญ๋น๊ฐ ์ฌํ๊ณ , ๋ด๋ถ ๋
ธ๋์ ์ธ๋ถ ๋
ธ๋๋ฅผ ๋๋์ด ๊ด๋ฆฌํด์ผ ํ๋ฏ๋ก ํ๋ก๊ทธ๋๋ฐํ๊ธฐ๊ฐ ์ด๋ ค์
ํจํธ๋ฆฌ์ค ํธ๋ฆฌ (Patricia)
์ธ๋ถ ํ์ (external seraching)
- ๋งค์ฐ ํฐ ํ์ผ์ ์๋ ๋ฐ์ดํฐ์ ๋น ๋ฅด๊ฒ ์ ๊ทผํ๋ ๊ฒ์ ๋ง์ ์์ฉ์์ ๋งค์ฐ ์ค์ํจ
- ์ธ๋ถ ํ์์ ํฐ ๋์คํฌ ํ์ผ์ ์ฃผ๋ก ๋ค๋ฃธ
- ํ
์ดํ ๊ฐ์ ์์ฐจ ์ ๊ทผ ์ฅ์น๋ ์์ฐจ ํ์ ์ธ์ ๋ณ๋ค๋ฅธ ํ์ ๋ฐฉ๋ฒ์ด ์์
- ์ธ๋ถ ํ์ ๊ธฐ๋ฒ์ ์ด๋ฏธ ๋ฐฐ์ด ๋ด๋ถ ํ์ ๊ธฐ๋ฒ์ ๋
ผ๋ฆฌ์ ํ์ฅ์
- 10์ต๊ฐ ์ด์์ ๋ฐ์ดํ๋ฅผ ํ์ํ๋๋ฐ ๋ถ๊ณผ 2โผ3ํ์ ๋์คํฌ ์ ๊ทผ์ผ๋ก ๊ฐ๋ฅํจ
- ๋์คํฌ๋ ํ์ด์ง๋ก ๊ตฌ๋ถ๋์ด ์์ผ๋ฉฐ, ํ์ด์ง๋ ๋ง์ ๋ ์ฝ๋๋ฅผ ๊ฐ์ง๊ณ ์์
B-tree
- Visualization : B-tree (์ด๊ธฐ ๋ก๋ฉ๋๋ฆผ ์ฃผ์)
B+-tree
- Knuth๊ฐ ์ ์ํ B-tree์ ๋ ๋ค๋ฅธ ๋ณํ ๊ตฌ์กฐ
- Index set & Sequence set๋ก ๊ตฌ์ฑ
- ๋ชฉ์ : ์์ฐจ ํ์์ ์ฑ๋ฅ ํฅ์(B-tree์ ์์ฐจ ํ์ ๋ณด์)
- ์ธ๋ฑ์ค ์ธํธ (index set)
- ๋ฆฌํ ์ด์ธ์ ๋
ธ๋
- ๊ตฌ์กฐ : ํค ๊ฐ๋ง ์กด์ฌ(๋ฆฌํ ๋
ธ๋์ ๋ํ ๊ฒฝ๋ก๋ง ์ ๊ณต)
- ์์ฐจ ์ธํธ (sequence set) - ๋ฆฌํ ๋
ธ๋
- ๊ตฌ์กฐ : ๋ชจ๋ (ํค๊ฐ, ๋ฐ์ดํ ๋ ์ฝ๋์ ์ฃผ์)๋ค์ด ์กด์ฌ
B+-tree์ ์ฑ๋ฅ (B-tree์์ ๋น๊ต)
- ํน์ ํค ๊ฐ์ ๊ฒ์
- ๋จ์
- ๊ฒ์์ด ํญ์ ๋ฆฌํ ๋
ธ๋๊น์ง ๋ด๋ ค๊ฐ์ผ๋ง ์ข
๋ฃ (ํญ์
O(log n))
- ๊ฒ์ํ๊ณ ์ ํ๋ ๊ฐ์ด ์ธ๋ฑ์ค ์ธํธ์์ ๋ฐ๊ฒฌ๋๋๋ผ๋ ๋ฆฌํ ๋
ธ๋๊น์ง ๋ด๋ ค๊ฐ์ผ๋ง ์ค์ ๋ ์ฝ๋์ ํฌ์ธํฐ๋ฅผ ์ ์ ์์
- ์ฅ์
- ์ธ๋ฑ์ค ๋
ธ๋๋ ํฌ์ธํฐ๋ฅผ ์ ์ฅํ์ง ์์ผ๋ฏ๋ก ๋
ธ๋ ๋ด ๊ณต๊ฐ์ด ์ ์ฝ๋จ โ ํธ๋ฆฌ๋ ๋ฒจ์ด ๋ฎ์์ง ์ ์์
- ๋ฒ์ ๊ฒ์
- ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ํ โ ํจ์จ์
- B+-ํธ๋ฆฌ๋ ํค ๊ฒ์๊ณผ ๋ฒ์ ๊ฒ์์ ๋ชจ๋ ํ์๋ก ํ๋ ์์ฉ์์ ํจ์จ์
R-tree
- B-tree๋ฅผ ๋ค์ฐจ์์ผ๋ก ํ์ฅ์ํจ ์์ ๊ท ํ ํธ๋ฆฌ
- ์ , ๋ฉด, ๋ํ ๋ฑ ๋ค์ํ ๋ค์ฐจ์ ๊ณต๊ฐ ๋ฐ์ดํฐ์ ์ ์ฅ์ด ๊ฐ๋ฅ(SAM)
- ํน์ง
- ๋ฃจํธ ๋
ธ๋๊ฐ ์๋ ๋
ธ๋๋ ์ต์ m, ์ต๋ M๊ฐ์ ์ํธ๋ฆฌ๋ฅผ ํฌํจํ๋ค. (m <= M/2)
- ๋ฃจํธ๋
ธ๋๋ ๋จ๋ง์ด ์๋ ๊ฒฝ์ฐ ์ต์ 2๊ฐ์ ์ํธ๋ฆฌ๋ฅผ ํฌํจํ๋ค.
- ์์ ๊ท ํํธ๋ฆฌ(๋ชจ๋ ๋จ๋ง ๋
ธ๋๋ ๊ฐ์ ๋ ๋ฒจ)์ด๋ค.