none
索引的结构是B树还是B+树? RRS feed

  • 问题


  • MSDN上面的写的是B树。

    但是B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历.

    如下图,SQL SERVER 更符合右边的图。因为SQL SERVER 中ID =5,对于键值5在非叶子节点有,在叶子节点也有。

    2016年12月21日 9:52

全部回复

  • 确定是B+ Tree。但是……B+ Tree也是B Tree啊,你说的区别是不对的,B Tree是指Balanced tree。

    是不是B Tree,跟中间节点有没有数据没关系。


    想不想时已是想,不如不想都不想。

    2016年12月22日 6:31
    版主
  • Hi owen_zeng,

    关于B 树和B+ 的区别,你可以先看看如下这个帖子。据此,我个理解是B+树的中间节点不包含数值, B树的中间节点包含。B+ 树的叶子节点相链接,而B树的叶子节点不链接。

    http://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees

    此外,我搜索到一篇介绍两者区别的博客,你可以看下。

    http://www.cnblogs.com/vincently/p/4526560.html

    关于SQL Server聚集索引非聚集索引,你可以看下如下的参考这篇博客另外这一篇。从中,我们可以知道SQL Server的索引中,叶子节点并没有链式关系, 并且中间节点仅仅包含数据位置指针键值 。

    The root and intermediate level nodes contain index pages holding index rows. Each index row contains a key value and a pointer to either an intermediate level page in the B-tree, or a data row in the leaf level of the index.

    This response contains a reference to a third party World Wide Web site. Microsoft is providing this information as a convenience to you. Microsoft does not control these sites and has not tested any software or information found on these sites; therefore, Microsoft cannot make any representations regarding the quality, safety, or suitability of any software or information found there. There are inherent dangers in the use of any software found on the Internet, and Microsoft cautions you to make sure that you completely understand the risk before retrieving any software from the Internet.

    Best Regards,

    Albert Zhang


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    • 已编辑 Albert_ Zhang 2016年12月27日 5:25 修改不准确的描述
    2016年12月22日 6:31
  • 你是不是把B tree和B-tree搞混了?

    想不想时已是想,不如不想都不想。

    2016年12月22日 6:34
    版主
  • 非常感谢回复!BTREE确实是指Balanced tree。但是BTREE 和B+ TREE是不一样.从维基百科可以看到不同点,但具体的不同我现在不是很明白,所以想请教下。上面的贴图,我是从一个博客上面贴的。
    2016年12月22日 10:07
  • 或者你可以这样理解,B Tree是一类数据结构,但是具体实现的时候,因为考虑到不同用途,所以有不同的实现方式,这些就叫B+Tree, B-Tree。

    B Tree一开始实现的就是B-Tree,后来才发展出来B+Tree的。

    顺便再提一句,SQL Server里面也用到B-Tree的。当然,索引是B+Tree。


    想不想时已是想,不如不想都不想。

    2016年12月22日 13:51
    版主
  • 非常感谢你的回复!你搜的B树和B+树的区别和我贴图是一致的。可能我问题描述的不是很清楚,我再描述下。

    1.B树和B+树是不同的东西。

    2.关于聚集索引的结构,官网文档原文描述如下

    In SQL Server, indexes are organized as B-trees. Each page in an index B-tree is called an index node. The top node of the B-tree is called the root node. The bottom level of nodes in the index is called the leaf nodes. Any index levels between the root and the leaf nodes are collectively known as intermediate levels. In a clustered index, the leaf nodes contain the data pages of the underlying table. The root and intermediate level nodes contain index pages holding index rows. Each index row contains a key value and a pointer to either an intermediate level page in the B-tree, or a data row in the leaf level of the index. The pages in each level of the index are linked in a doubly-linked list.

    这里描述的是: 所有的 索引页 都是通过双向链表链接在一起的。而不是节点直接进行链接。之前,我把这里理解错了。认为是图中的第二种。

    补充问题:关于 中间节点包含数据位置指针这个有点疑问。上面的描述是,每个索引行包含指针,指向中间层页面或者数据页。

    如果这个指针是执行的中间层页面。那他就不是指向数据的位置了。这是B+的特征。

    2016年12月23日 1:24
  • 感谢,但是 官网说明文档写的聚集索引就是B TREE。详细的见我上面的回复。
    2016年12月23日 1:25
  • Hi owen_zeng,

    Sorry,我已经更该了之前的描述。我又查看了一些文档,个人觉得索引的描述像是B+ Tree。不过根据如下B+ Tree的描述,B+ Tree 可以被看作是B Tree的一种特殊形式。

    A B+ tree can be viewed as a B-tree in which each node contains only keys (not key-value pairs), and to which an additional level is added at the bottom with linked leaves.

    https://en.wikipedia.org/wiki/B%2B_tree

    Best Regards,

    Albert Zhang


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    2016年12月27日 5:25
  • 确定是B+Tree,我跟写这块的人聊过。不过B-Tree和B Tree的定义本来就有点模糊。

    想不想时已是想,不如不想都不想。

    2016年12月27日 9:44
    版主
  • 是啊,本来这2个很容易迷惑。官网上显示的还是B树。让我感觉被搞晕了
    2016年12月30日 8:48