Question: So I was reading up on indexes and their implementation, and I stumbled upon this website that has a brief explanation of b-tree indexes:

<http://20bits.com/articles/interview-questions-database-indexes/>

The b-tree index makes perfect sense for indexes that are only on a single column, but let's say I create an index with multiple columns, how then does the b-tree work? What is the value of each node in the b-tree? 

For example, if I have this table:

```
table customer:
id    number
name   varchar
phone_number   varchar
city   varchar

```

and I create an index on: (id, name, city) 

and then run the following query:

```
SELECT id, name 
  FROM customer
 WHERE city = 'My City';

```

how does this query utilize the multiple column index, or does it not utilize it unless the index is created as (city, id, name) or (city, name, id) instead?

Answer: 
Some implementations simply concatenate the values in the order of the columns, with delimiters.

Another solution is to simply have a b-tree within a b-tree. When you hit a leaf on the first column, you get both a list of matching records and a mini b-tree of the next column, and so on. Thus, the order of the columns specified in the index makes a huge difference on whether that index will be useful for particular queries.

Here's a related question I wrote last week:

[Does SQL Server jump leaves when using a composite clustered index?](https://stackoverflow.com/questions/1615893/does-sql-server-jump-leaves-when-using-a-composite-clustered-index)
Other than the "composite key" mechanism already described, one possibility is a `kdtree` which works like a binary tree, but as you traverse each level you cycle through `k` dimensions. That is, the first level of the tree separates the first dimension into two parts, the second level splits the second dimension, the `k+1`th level splits the first dimension again, etc.. This allows for efficient partitioning of data in any number of dimensions. This approach is common in "spatial" databases (e.g., Oracle Spatial, PostGIS, etc.), but probably not as useful in "regular" multi-indexed tables.

<http://en.wikipedia.org/wiki/Kd-tree>