Transcript Hash/B+ Tree/R Tree

Hash/B+ Tree/R Tree
Muneeb Mahmood
Ashfaq Ahmed
Jim Kang
Outline






Hash Table
B+ Tree
R – Tree
SQL Parser
Demo
Performance
Project Functionality – Hash
Table

Developed by Ashfaq Ahmed

Indexing Scheme: Hash Maps
Load Indexes
For all the attributes
Select Queries of both Still and Motion
Multiple Conditions using And/Or
Insert
At the end of the file/ update indexes
Hash Table Contd..
Update
Index gets updated
Delete
Index gets updated
Hash Table contd..
Performance:
Used Random Access File to access
Stored Line Numbers in the Hash Map
Problems:
While reading the flat file
Adding junk characters at the end of file
Pointing to specific location ( random access)
Implementation of B+ and R
Trees

Presented by Muneeb

GiST

Generalized Search Tree

Developed by University of California, Berkley

Can be used to represent all types of search trees








Binary Search Trees
B+ Trees
R Trees
hBTrees
TV Trees
Ch Trees
Partial Sum Trees
etc.
Implementation of B+ and R
Trees

Specific implementations of GiST


BT package (for B+ Trees)
RS package (for R Trees)

Developed at CS department of University of
Cape Town

Written using a version of persistent java called
PJama
Implementation of B+ Tree
Index

Indexing was implemented on all the attributes of both still and motion table

Each index was stored in the form a B+ Tree

Root

Nodes – Min. occupancy = 2
Max. occupancy = 4
Points to sub nodes

Leaves – Have no sub nodes
- Stores the data ( line numbers)

Random access to data file

Indexing used for:




Select
Insert
Update
Delete
Project Functionality – B+ Tree
Developed by Muneeb



1) Select :
 Supports searching of both still and motion tables
 Support complicated searching with an AND or OR
Where statement
after
2) Insert:
 Supports insertion into both still and motion tables
 Inserts dynamically into database and same time indexes
the new tuple
Project Functionality – B+ Tree
Developed by Muneeb


3) Update:
 Supports updates for still table
 Support complicated updating with an AND or OR after
Where statement
 Dynamically updates both database file and index

4) Delete:
 Supports updates for both still and motion tables
 Support complicated deleting with an AND or OR after
Where statement
 Dynamically updates both database file and index
Project Functionality – B+ Tree
Developed by Muneeb


BPlusTreeIndexprinter

Utility that prints out the B+Tree Index on a specified
attribute of still or motion table

Displays
- The root node
- The sub nodes
- Leaves
- Data stored in the leaves




Implementation of R Tree
Index

Goal: Create an index on each pair of
attributes to make search time optimal

Problem: Because queries can be in any order,
need to take care of every combination.



Still Table: 11 attributes -> 121 Indexes
Motion Table: 6 attributes -> 36 Indexes
Solution: Create one index for each attribute
Differences between B+ and R
Tree

Queries done on R Trees are executed as
Ranges. Our test show that R Trees perform
better than Hash and B+ Tree. (10 Tests)
Project Functionality – R Tree
Developed by Jim Kang



1) Select :
 Supports searching of both still and motion tables
 Support complicated searching with an AND or OR
Where statement
after
2) Insert:
 Supports insertion into both still and motion tables
 Inserts dynamically into database and same time indexes
the new tuple
Project Functionality – R Tree
Developed by Jim Kang


3) Update:
 Supports updates for still table
 Support complicated updating with an AND or OR after
Where statement
 Dynamically updates both database file and index

4) Delete:
 Supports updates for both still and motion tables
 Support complicated deleting with an AND or OR after
Where statement
 Dynamically updates both database file and index
SQL Functionality

Developed by Jim Kang using ZQL

SQL Parser
 Parses SQL using ZQL
 Complete Error Checking
Select Queries
 AND/OR within where statements
 Including Update and Delete
Insert
 Inserts into File and index, Still and Motion
Update
 Updates into File and index, Still and Motion
 (Update file done by B+ and R Tree only)
Delete
 Deletes from File and index, Still and Motion
 (Delete from file done by B+ and R Tree only)




Demo
Performance
Load Time
Load Time for Still and Motion
600
500
ms

400
Hash Tree
300
B+ Tree
200
R Tree
100
0
Index
Performance
Average Select Query Performance (20 test
Queries)
Average Query Performance
2100
2000
ms

1900
Hash Table
1800
B+ Tree
1700
R Tree
1600
1500
Index
Performance
Update Time for 1 tuple
Update Performance
ms

90
80
70
60
50
40
30
20
10
0
Hash Table
B+ Tree
R Tree
Index
Performance
Insert Time for 1 tuple
Insert Performance
25
20
ms

Hash Table
15
B+ Tree
10
R Tree
5
0
Index
Performance
Delete Time for 1 tuple
Delete Performance
100
80
ms

Hash Table
60
B+ Tree
40
R Tree
20
0
Index
Performance
Average Query Range Time
Average on Query Ranges
ms

2150
2100
2050
2000
1950
1900
1850
1800
1750
1700
Hash Table
B+ Tree
R Tree
Index
References

http://www.experlog.com/gibello/zql/

http://gist.cs.berkeley.edu:8000/gist/

http://people.cs.uct.ac.za/~evoges/web/Paper
/p.html

Help from Yan Hu on R Trees. Thanks!