it is a special kind of database optimized for storing and analyzing time-indexed data which are data points that specifically occur at a given moment in time
use cases
good if you are monitoring parts of the system
e.g: a bunch of events that all occur at a given timestamp
if you are designing an IoT system, where you got millions of devices that are constantly sending telemetry data or capturing certain data in their environments
if you are dealing with stock prices that change every second or cryptocurrency prices
a type of database that stores data following the graph data model
data entries in a graph database can have explicitly defined relationships
much like nodes in a graph can have edges
graph databases take advantage of their underlying graph structure to perform complex queries on deeply connected data very fast
graph database are thus often preferred to relational databases when dealing with systems where data points naturally form a graph and have multiple levels of relationships
there might be times where you might need to implement your own spatial indexes and storing it in memory
might be required if you are designing a system that really cares about very fast latencies, dealing with location based system or system that relies on spatial data, and you don't wanna be querying the database all the time
in this day and age, a lot of databases e.g.: Postgres are smart and really optimized for all sorts of queries and data types
thus is possible that some databases like Postgres might provide out of the box solutions for spatial data
this is dependent on the interviewer, discuss with the interviewer to understand what they are looking for
a tree data structure most commonly used to index 2 dimensional spatial data
each node in a quadtree has either 0 children nodes (and is therefore a leaf node) or exactly 4 children nodes
typically quadtree nodes contain some form of spatial data
e.g.: locations on a map with a maximum capacity of some specified number n
so long as nodes aren't at capacity, they remain leaf nodes
once they reach capacity, they're given 4 children nodes, and their data entries are split across 4 children nodes
a quadtree lends itself well to storing spatial data because it can be represented as a grid filled with rectangles that are recursively subdivided into 4 sub-rectangles
where each quadtree node is represented by a rectangle and each rectangle represents a spatial region
assuming we're storing locations in the world, we can imagine a quadtree with a maximum node-capacity n as follows
the root node, which represents the entire world, is the outermost rectangle
if the entire world has more than n locations, the outmost rectangle is divided into 4 quadrants, each representing a region of the world
so long as a region has more than n locations, its corresponding rectangle is subdivided into 4 quadrants (the corresponding node in the quadtree is given 4 children nodes)
regions that have fewer than n locations are undivided rectangles (leaf nodes)
the parts of the grid that have many subdivided rectangles represent densely populated areas (like rural areas)
finding a given location in a perfect quadtree is an extremely fast operation that runs in log4(x) time (where x is the total number of locations), since quadtree nodes have 4 children nodes