Binary-tree lookup.....

Is SQL Server 2000 has been optimized to allow binary-tree lookup in the
index table ?
Thanks,
John
Can you be rephrase the question? SQL Server always uses b-trees for it's
indexes.
Andrew J. Kelly SQL MVP
"John Smith" <JSmith_SJ@.hotmail.com> wrote in message
news:eAEQdz3PFHA.3596@.TK2MSFTNGP15.phx.gbl...
> Is SQL Server 2000 has been optimized to allow binary-tree lookup in the
> index table ?
> Thanks,
> John
>
|||SQL Server 2000 indexes are organized as B-trees. Details are available in
BOL.
joe.
"John Smith" <JSmith_SJ@.hotmail.com> wrote in message
news:eAEQdz3PFHA.3596@.TK2MSFTNGP15.phx.gbl...
> Is SQL Server 2000 has been optimized to allow binary-tree lookup in the
> index table ?
> Thanks,
> John
>
|||Is this way of indexing (B-trees) from the first release of SQL Server or is
got implemented in the subsequent releases of SQL Server?
Thanks for your feedback.
John
"Joe Yong" <NO_jyong_SPAM@.scalabilityexperts.com> wrote in message
news:J2T6e.10242$Zn3.2388@.trnddc02...
> SQL Server 2000 indexes are organized as B-trees. Details are available in
> BOL.
>
> joe.
> "John Smith" <JSmith_SJ@.hotmail.com> wrote in message
> news:eAEQdz3PFHA.3596@.TK2MSFTNGP15.phx.gbl...
>
|||The current way of implementing B-trees has been used since at least 7.0.
Earlier versions used B-trees as well but the underlying implementation of
data pages and indexes was somewhat different.
Andrew J. Kelly SQL MVP
"John Smith" <JSmith_SJ@.hotmail.com> wrote in message
news:%23jwyRl4PFHA.1500@.TK2MSFTNGP09.phx.gbl...
> Is this way of indexing (B-trees) from the first release of SQL Server or
> is
> got implemented in the subsequent releases of SQL Server?
> Thanks for your feedback.
> John
>
> "Joe Yong" <NO_jyong_SPAM@.scalabilityexperts.com> wrote in message
> news:J2T6e.10242$Zn3.2388@.trnddc02...
>
|||To expand a little bit. Earlier, the leaf level of a non-clustered index always had the physical
address of the row. As of 7.0, only non-clustered indexes over heap tables has the physical row
address. Non-clustered index on a table which has a clustered index has the clustered key in the
leaf level (the "row locator"). Apart from that, the implementation is the same (making both old and
new architecture be+ trees, methinks).
Tibor Karaszi, SQL Server MVP
http://www.karaszi.com/sqlserver/default.asp
http://www.solidqualitylearning.com/
"Andrew J. Kelly" <sqlmvpnooospam@.shadhawk.com> wrote in message
news:%23C%23Cc64PFHA.3668@.TK2MSFTNGP14.phx.gbl...
> The current way of implementing B-trees has been used since at least 7.0. Earlier versions used
> B-trees as well but the underlying implementation of data pages and indexes was somewhat
> different.
> --
> Andrew J. Kelly SQL MVP
>
> "John Smith" <JSmith_SJ@.hotmail.com> wrote in message
> news:%23jwyRl4PFHA.1500@.TK2MSFTNGP09.phx.gbl...
>
|||I think the term B-plus trees was used by Oracle. They are actually not
B-tree's because
they are not conform all requirements of B-tree's. A B-tree's node is
always filled for
at least (about) 50 percent (with exception of the root), where Oracle does
not reorganise during deletion and can get nodes filled for less than 50
percent.
For SQL-server I think they are not 'pure' B-tree's either, because in the
'original'
description (Knut) of B-tree's the nodes contain pointer or date information
as wel
and not only the leaves. I think in SQL-server that all information is
present in the leaves.
(In Knut's implementation the info which was in the nodes (or root) was not
repeated
in the leaves.).
One other 'enhancement' to the B-tree is that all leaves are single or
double linked, this
makes traversing the leaves (a bit) faster. But then again all data has to
be present within
the leaves. (This has also a disadvantage (for older databases), in B-tree's
a complete
subtree of a b-tree can be replaced with only one update, when the leaves
are linked this is not
possible anymore).
Knut describes the B-tree with only a few rules, one of the key rules is
that all
nodes and leaves (except the root) are filled for at least (about) 50
percent. The tree can
only gain or lose a level at the root, so all leaves have the same distance
from the
root. (I think that SQL-server conforms to these rules, but not to all
rules.).
ben brugman
"Tibor Karaszi" <tibor_please.no.email_karaszi@.hotmail.nomail.com> schreef
in bericht news:eBkiCT5PFHA.2604@.TK2MSFTNGP10.phx.gbl...
> To expand a little bit. Earlier, the leaf level of a non-clustered index
always had the physical
> address of the row. As of 7.0, only non-clustered indexes over heap tables
has the physical row
> address. Non-clustered index on a table which has a clustered index has
the clustered key in the
> leaf level (the "row locator"). Apart from that, the implementation is the
same (making both old and[vbcol=seagreen]
> new architecture be+ trees, methinks).
> --
> Tibor Karaszi, SQL Server MVP
> http://www.karaszi.com/sqlserver/default.asp
> http://www.solidqualitylearning.com/
>
> "Andrew J. Kelly" <sqlmvpnooospam@.shadhawk.com> wrote in message
> news:%23C%23Cc64PFHA.3668@.TK2MSFTNGP14.phx.gbl...
7.0. Earlier versions used[vbcol=seagreen]
indexes was somewhat[vbcol=seagreen]
or is[vbcol=seagreen]
available in[vbcol=seagreen]
the
>
|||Well all I know is that the SQL developers call it a B-Tree. How it is
implemented as compared to others I don't really know or care<g>.
Andrew J. Kelly SQL MVP
"Ben Brugman" <Ben@.niethier.nl> wrote in message
news:fsSdnenUYu-7usHfRVnyuw@.casema.nl...
>I think the term B-plus trees was used by Oracle. They are actually not
> B-tree's because
> they are not conform all requirements of B-tree's. A B-tree's node is
> always filled for
> at least (about) 50 percent (with exception of the root), where Oracle
> does
> not reorganise during deletion and can get nodes filled for less than 50
> percent.
> For SQL-server I think they are not 'pure' B-tree's either, because in the
> 'original'
> description (Knut) of B-tree's the nodes contain pointer or date
> information
> as wel
> and not only the leaves. I think in SQL-server that all information is
> present in the leaves.
> (In Knut's implementation the info which was in the nodes (or root) was
> not
> repeated
> in the leaves.).
> One other 'enhancement' to the B-tree is that all leaves are single or
> double linked, this
> makes traversing the leaves (a bit) faster. But then again all data has to
> be present within
> the leaves. (This has also a disadvantage (for older databases), in
> B-tree's
> a complete
> subtree of a b-tree can be replaced with only one update, when the leaves
> are linked this is not
> possible anymore).
> Knut describes the B-tree with only a few rules, one of the key rules is
> that all
> nodes and leaves (except the root) are filled for at least (about) 50
> percent. The tree can
> only gain or lose a level at the root, so all leaves have the same
> distance
> from the
> root. (I think that SQL-server conforms to these rules, but not to all
> rules.).
> ben brugman
> "Tibor Karaszi" <tibor_please.no.email_karaszi@.hotmail.nomail.com> schreef
> in bericht news:eBkiCT5PFHA.2604@.TK2MSFTNGP10.phx.gbl...
> always had the physical
> has the physical row
> the clustered key in the
> same (making both old and
> 7.0. Earlier versions used
> indexes was somewhat
> or is
> available in
> the
>
sql