Study/SDBMS8 SDBMS ⑧ The R-Tree - Search, Delete, Variations SDBMS 공간데이터 베이스 ⑧ The R-Tree Search, Delete, Variations Recall R-tree의 노드는 { mbr, node pointer } 로 표현하며 leaf 노드의 entry는 각 객체와 대응한다. 각 노드의 자식 노드 mbr은 부모 노드 mbr에 포함된다. Insert 및 split 시 R tree는 같은 깊이 노드 mbr이 최대한 겹치지 않는 방향으로 작동한다. 4. Search R-tree에서 search 역시 mbr을 활용하여 진행한다. Search(R) Root의 자식 노드 중 범위 R과 겹치는(overlap) 노드에 대해서 해당 노드의 자식 노드 중 범위 R과 겹치는 노드를 찾는 과정을 반복한다. 해당 노드가 leaf 노드일 때 집합에 entry를 추가하고.. 2021. 8. 26. SDBMS ⑧ The R-Tree - Insert, Split SDBMS 공간데이터베이스 ⑧ The R-Tree Insert, Split 0. Data Driven Structure 객체를 기준으로 인덱싱하는 구조 객체 주변에 존재하는 객체가 서로의 인덱싱에 영향을 준다. 위치를 기준으로 인덱싱(: Space Driven Structure)하지 않음. 1. R-Tree : MBR을 이용하여 다차원 데이터를 관리하는 data driven structure 아래 특징에 의해 R-Tree는 트리 빌드와 쿼리 수행에서 일정 수준 이상의 성능을 보장한다. - Root 노드는 최소 2개의 자식 노드를 가진다. - Root가 아닌 non-leaf 노드는 최소 m, 최대 M개의 자식 노드를 가진다. - Leaf 노드는 최소 m, 최대 M개의 entry를 저장한다. - Leaf 노.. 2021. 8. 9. SDBMS ⑥ The KD Tree SDBMS 공간데이터베이스 ⑥ The KD Tree 1. KD Tree : $k$-d tree, $k$-dimentional tree $k$차원의 점을 관리하는 이진 트리 구조이다. 트리의 모든 leaf는 $k$차원의 점이고 non-leaf는 공간을 나누는 hyperplane*이다. * 본래 공간보다 한 차원 하위의 공간이라고 생각하면 될 듯. 3차원이라면 평면, 2차원이라면 선분 등 기본적으로는 중앙값을 기준으로 점을 두 영역에 나누고, 또 중앙값을 기준으로 나누는 걸 반복해 leaf에 한 개의 점이 할당될 때까지 재귀적으로 트리를 빌드한다. 위 그림에서는 $x$를 기준으로 먼저 축을 골라 ①의 좌우로 점들을 나누고 다음 단계에서는 $y$를 기준으로 축을 골라 점을 나눴다. 다시 $x$, $y$, $x.. 2021. 4. 15. SDBMS ⑤ The Z-Ordering Tree SDBMS 공간데이터베이스 ⑤ The z-Ordering Tree 0. Z-Ordering 여러 개의 quadrant를 이용하여 하나의 다각형을 mbb가 아닌 형태로 나타낼 수 있다. degree=3으로 공간을 나눈 경우 가장 작은 quadrant는 전체 공간의 1/64 크기가 되고 label 길이는 3이 된다. 이때 도형 A의 경우 위처럼 표현할 수 있다. 만약 degree=2로 공간을 나눴다면 A={01,02,03,12,20,21,23,31}가 된다. 이런 방식으로 객체 정보를 저장하고 인덱싱 한 게 Z-Ordering Tree이다. 1. The Z-Ordering Tree Z-Ordering tree는 linear quadtree와 마찬가지로 quadrant의 label을 key로 하는 B+tree.. 2021. 4. 8. SDBMS ④ The Linear Quadtree SDBMS 공간데이터베이스 ④ The Linear Quadtree 0. The Quadtree 공간을 사분할하여 데이터를 저장하는 구조 단순하게 NW, NE, SW, SE로 사분할하여 공간 상에서의 quadrant ↔ 트리의 leaf node ↔ page 로 대응, quadrant와 겹치는 데이터의 [mbr,oid]를 해당 page에 저장한다. 아주 직관적이고 구현이 쉽다. 그러나 - node 당 child의 수가 4개로 고정되어있다. 빈 quadrant에 대응되는 node도 생겨 page waste 발생 - quadrant가 작을수록 겹치는 게 많아 중복저장이 증가한다. (grid file에서와 같음.) - 한쪽으로 데이터가 집중될 경우 leaf node의 깊이가 각각 달라진다. 따라서 (B+tree와.. 2021. 4. 2. SDBMS ③ SAM, The Grid File SDBMS 공간데이터베이스 ③ SAM, The Grid File 0. SAM The main purpose of spatial access methods is to support efficient selection of objects based on spatial properties. * SAM = 공간적 특성이 있는 객체를 좀 효율적으로 고르는 방법. 이라고 이해하면 된다. 점, 선, 면을 object자체보다 단순화해서 MBR(Minimum Bounding Rectangle)이나 MBB(Minimum Bounding Box)로 나타내는 방법을 사용하면 복잡한 도형도 간단히 표시할 수 있고, 일정한 크기의 entry로 사용할 수 있다는 장점이 있다. 즉 각 entry의 자세한 정보는 page에 저장하고 .. 2021. 3. 29. SDBMS ② ER Diagram and Relational Schema SDBMS 공간데이터베이스 ② ER Diagram and Relational Schema ER Diagram 데이터 모델의 entity를 직사각형, attribute를 타원, relationship를 마름모로 표현한 그림. Pictogram을 이용해 객체의 공간적 정보를 나타낼 수도 있다. Relational Schema 데이터 모델을 logical model로 나타낸 것. Logical model을 디자인할 때는 relationship을 entity로 표현할 지, attribute로 표현할 지가 관건이다. ...그냥 그림을 보자... 각 그림을 비교해서 무얼 어떤 식으로 나타냈는지 보면 된다. E를 ER Diagram, R을 Relational Schema, P를 ER Diagram with Picto.. 2021. 3. 15. SDBMS ① Spatial Data Model and Topological Relationship SDBMS 공간데이터베이스 ① Spatial Data Model and Topological Relationship 1. Data Model 데이터를 활용하기 위한 데이터 모델은 여러 종류가 있겠으나 일반적인 데이터 모델은 Spatial ADT 지원이 안 돼 공간적 데이터에는 적합하지 않다. 이 과목에서 다루는 내용은 Applicatoin Domain specific한 데이터 모델 *ADT: Abstract Data Type *Application Domain specific: 솔직히 이 말 잘 이해 못하겠으나,, '지리적 정보에 대한 개념이 탑재된' 정도로 이해하면 될 듯 Spatial 모델은 위치에 초점을 두느냐 객체에 초점을 두느냐로 나눠 생각할 수 있다. 이 글에서 주로 설명할 건 object b.. 2021. 3. 15. 이전 1 다음
