1
$\begingroup$

Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following:

CREATE TABLE foo (
  x int,
  y int
)

SELECT * FROM foo
  WHERE x > 10 AND x < 100
    AND y > 20 AND y < 200

From my understanding this would require 2 b+trees, one for each property ($x$ and $y$). Wondering if one could describe how it would go about about querying the different indexes to satisfy this query. I am having difficulty understanding how the B+tree works in practice.

$\endgroup$
1
$\begingroup$

This is up to the individual database system. There are multiple ways one might index the data and support this type of query.

One natural approach is that the system might compute in advance an index over the x-values (i.e., a B+ tree that is keyed by the x values) and a second index over the y values (i.e., a B+ tree that is keyed by the y values). Given those indices, you can now implement the search query by doing a range query on the first B+ tree to find all values where x > 10 AND x < 100, then iterate through them and keep the ones that also satisfy y > 20 AND y < 200.

It is also possible to build multi-dimensional data structures that support 2D range queries, but those are more complex and might not be used in a typical database system.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.