数据结构~Sqlserver索引使用的B树
栏目: 数据库 · SQL Server · 发布时间: 6年前
内容简介:数据结构~Sqlserver索引使用的B树
B树相关概念
在B-树中查找给定 关键字 的方法是,首先把根结点取来,在根结点所包含的关键字K1,…,Kn查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查找的关键字在Ki与Ki+1之间,Pi为指向子树根节点的指针,此时取 指针 Pi所指的结点继续查找,直至找到,或指针Pi为空时查找失败。
时间复杂度
动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree), 红黑树 (Red-Black Tree ),B-tree/B + -tree/ B * -tree (B~Tree)。前三者是典型的二叉查找树结构,其查找的时间复杂度
O (log 2 N )
与树的深度相关,那么 降低树的深度自然会提高查找效率 。
在SQLSERVER里的表现
我们都知道sqlserver数据行的存储结构有两种:堆(heap)和B树(binary二叉树)。学过数据结构的人都知道,二叉树的优点是: 快速使用二分法找到数据 ,数据页面使用 双向链表 首尾相连。再介绍一下数据结构中的堆(heap)。堆中的数据没有任何顺序,数据页面也不会首尾相连。那怎么在堆中查找数据呢? 堆的结构及IAM结构如下:
堆表只依靠表里的IAM页(索引分配映射页)将堆的页面联系在一起,IAM中记录了页面编号和页面位置。由此可以通过IAM扫描数据。
1.很多书中都讲到sqlserve r数据行的存储结构有两种:堆(heap)和B树 (binary二叉树)。 而我觉得sqlserver数据页的存储结构有两种:堆(heap)和B树(binary二叉树) 。
2.数据都存在页面中,sqlserver页面有两种类型:数据页和索引页。索引页都是按照B树结构存储的。
那么重点来了:
不管是聚集索引,还是非聚集索引,索引数据都存放在索引页中。
表中如果有聚合索引,那么数据全部存储在索引页中。
表中如果只有有非聚合索引,那么数据存在堆页(也就是实际的数据行),但是索引数据存储在索引页中。
表中如果既有聚集索引,也有非聚集索引,那么数据和索引都存放在索引页中。
B树结构中,每一个节点就是一个页面,B树里会有一页:root page(亦即是根节点),非聚集索引和聚集索引都是一样的。
下面开始步入正轨介绍索引:
聚集索引:
有人会问为什么一张表只能有一个聚集索引,简单来说因为表只能以一种顺序排列在磁盘中,所以表只能有一个聚集索引。而非聚集索引能有好几个。
聚集索引因为数据全部存放在索引页中,所以顺着聚集索引就可以查到数据。聚集索引结构如下:
非聚集索引
1.如果非聚集索引的数据放在堆表中(表示没有聚集索引),而非聚集索引的数据放在索引页中。那么非聚集索引怎么查找数据呢?在非聚集索引的叶子节点(即叶子页面)有行定位器,行定位器指向行的位置。由文件标示符、页码、行上的行数组成。整个指针称为行ID(RID)。
2.如果非聚集索引的数据放在索引表中(表示有聚集索引),那怎么查找数据呢?则行定位器会指向聚集索引键。SQL使用非聚集索引叶子节点的指针指向的聚集索引键值,来查找数据。
感谢各位的阅读,部分内容来自博客:http://blog.csdn.net/u014524247/article/details/40273773
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据库索引背后的数据结构
- 深入理解 MySQL 索引底层数据结构
- 深入理解 MySQL 索引底层数据结构
- MySQL索引背后的数据结构及算法原理
- MySQL索引背后的数据结构及算法原理
- MySQL索引使用说明(单列索引和多列索引)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
JAVA多线程设计模式
结城 浩、博硕文化 / 博硕文化 / 中国铁道出版社 / 2005-4-1 / 49.00元
《JAVA多线程设计模式》中包含JAVA线程的介绍导读,12个重要的线程设计模式和全书总结以及丰富的附录内容。每一章相关线程设计模式的介绍,都举一反三使读者学习更有效率。最后附上练习问题,让读者可以温故而知新,能快速地吸收书中的精华,书中最后附上练习问题解答,方便读者学习验证。一起来看看 《JAVA多线程设计模式》 这本书的介绍吧!
UNIX 时间戳转换
UNIX 时间戳转换
RGB HSV 转换
RGB HSV 互转工具