Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

what does a B-tree index on more than 1 column look like?

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?

like image 545
Lawrence Avatar asked Oct 30 '09 05:10

Lawrence


People also ask

Can multiple columns have same index?

For example, if you have an index on column {a} or columns {a,b}, you can't create another index on the same column or set of columns in the same order. In 12c, you can have multiple indexes on the same column or set of columns as long as the index type is different.

How many columns can be in an index?

9 Replies. 1. 1-254 columns can be created in a table.

How do you look up values when using B-tree indexes?

Each of the leaf nodes has reference to the next record in the tree. A database can perform a binary search by using the index or sequential search by searching through every element by only traveling through the leaf nodes. If no indexing is used, then the database reads each of these records to find the given record.

How are B-tree used in multi level indexing for index sequential file organization?

B+ tree file organization is the advanced method of an indexed sequential access method. It uses a tree-like structure to store records in File. It uses the same concept of key-index where the primary key is used to sort the records. For each primary key, the value of the index is generated and mapped with the record.


2 Answers

With most implementations, the key is simply a longer key that includes all of the key values, with a separator. No magic there ;-)

In your example the key values could look something like

 "123499|John Doe|Conway, NH" "32144|Bill Gates| Seattle, WA" 

One of the characteristics of these indexes with composite keys is that the intermediate tree nodes can be used in some cases to "cover" the query.

For example, if the query is to find the Name and City given the ID, since the ID is first in the index, the index can search by this efficiently. Once in the intermediate node, it can "parse" the Name and City, from the key, and doesn't need to go to the leaf node to read the same.

If however the query wanted also to display the phone number, then the logic would follow down the leaf when the full record is found.

like image 64
mjv Avatar answered Sep 30 '22 22:09

mjv


Imagine that the key is represented by a Python tuple (col1, col2, col3) ... the indexing operation involves comparing tuple_a with tuple_b ... if you have don't know which value of col1 and col2 that you are interested in, but only col3, then it would have to read the whole index ("full index scan"), which is not as efficient.

If you have an index on (col1, col2, col3), then you can expect that any RDBMS will use the index (in a direct manner) when the WHERE clause contains reference to (1) all 3 columns (2) both col1 and col2 (3) only col1.

Otherwise (e.g. only col3 in the WHERE clause), either the RDBMS will not use that index at all (e.g. SQLite), or will do a full index scan (e.g. Oracle) [if no other index is better].

In your specific example, presuming that id is a unique identifier of a customer, it is pointless to have it appear in an index (other than the index that your DBMS should set up for a primary key or column noted as UNIQUE).

like image 45
John Machin Avatar answered Sep 30 '22 22:09

John Machin