CSE 163

Indexes and Trees

��Hunter Schafer

​

​

​

​

​

​

💬 Before class: What is your favorite type of cloud?

🎵 Music: Work Wife

Binary Search Tree

Can build up a tree to help us search through sorted items

• Similar to a decision tree of sorts!

2

Spatial Join - Points

Imagine we had a dataset of where�people live in England.��Want to know if someone lives�at coordinates (x, y)��How many points would we �have to search through?

3

[Point1, Point2, Point3, …]

Spatial Index

4

Spatial Index

This forms a tree!

​

5

Spatial Index Visualization

How the splits are chosen is not discussed

6

Spatial Index Query

To find if a Point is in the dataset, follow the tree! Suppose we are looking for g (we know it’s coordinates, but not index)

​

​

7

Spatial Index Performance

• Say we are looking for a single Point
• How much work is it if we have n rows?
• Without a spatial index: O(n)
• With a spatial index? O(height of tree)
• How tall is the tree? How many times can we divide 1 million points in half?
• 1,000,000 / 2 / 2 / 2 / 2 / … / 2 = 1
• 2^k = 1,000,000
• k = log₂(1,000,000) ≅ 20
• This means the lookup is O(log n)
• A million doesn’t sound that big. What about a tree of the US?
• 327.2 million people
• log₂(327,200,000) ≅ 28
• The US isn’t THAT big. What about a tree of China?
• 1.386 billion people
• log₂(1,386,000,000) ≅ 30

8

Group Work:

Best Practices

When you first working with this group:

• Introduce yourself!
• If possible, angle one of your screens so that everyone can discuss together

​

Tips:

• Starts with making sure everyone agrees to work on the same problem
• Make sure everyone gets a chance to contribute!
• Ask if everyone agrees and periodically ask each other questions!
• Call TAs over for help if you need any!

9