Re: B-Tree's and internal DBMS implementations

"John" <JonJones(NOSPAM)_at_hotmail.com> wrote in message news:<auqvhv$3ng$1_at_news8.svr.pol.co.uk>...
> I'am somewhat curious about the B-tree algorithms and how RDBMS us them
> successfully. My question is, what is stored at the leaf level? ...
> How does the B-Tree deal with the LIKE clause, does that then cause a linear
> search through the tree?

In the most common structure, at the leaf level one has keys + addresses which some vendors call RIDs (Row Identifiers) and some vendors call ROWIDs. The address is a numeric identifier of the "file" (which may be database + table or may contain tablespace or partition), the page number (what some call a block number), and finally the row number within the page.

This is not possible with indexes to clustered or "Index-Organized Tables" (to use the Oracle term for a structure that's also in SQL Server and other DBMSs). There the only possible address would be the "cluster key" or the "primary key" contents, and some vendors have refused this fence because of the extra overhead involved in maintenance.

LIKE and SIMILAR TO and REGEXP operators will typically use the index if the first character in the pattern is non-wild. Naturally the decision whether to use an index depends on several other factors as well, though.

Peter Gulutzan
Co-Author of SQL Performance Tuning (http://www.ocelot.ca/tuning.htm) Received on Wed Jan 01 2003 - 19:09:29 CET