Path: news.easynews.com!newsfeed1.easynews.com!easynews.com!easynews!newsfeed.news2me.com!canoe.uoregon.edu!logbridge.uoregon.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail From: pgulutzan@ocelot.ca (Peter Gulutzan) Newsgroups: comp.databases.theory Subject: Re: B-Tree's and internal DBMS implementations Date: 1 Jan 2003 10:09:29 -0800 Organization: http://groups.google.com/ Lines: 24 Message-ID: <36c478c6.0301011009.2eba1d69@posting.google.com> References: NNTP-Posting-Host: 152.163.188.227 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: posting.google.com 1041444569 1256 127.0.0.1 (1 Jan 2003 18:09:29 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: 1 Jan 2003 18:09:29 GMT Xref: newsfeed1.easynews.com comp.databases.theory:24225 X-Received-Date: Wed, 01 Jan 2003 11:18:48 MST (news.easynews.com) "John" wrote in message news:... > 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)