SQLServer传统索引结构.ppt
大家好大家好1什么是数据库页面（SQL Server中有好几种页面类型）什么是B*树（数据结构：B*树 算法：二分查找法）什么是二分查找法（折半查找法）什么是堆表什么是聚集索引表2一句话和一个公式1、数据库里没有绝对地址，只有相对地址2、8KB*PAGENO=页面地址数据文件都可以除尽8KB索引页面和数据页面会有objectid3B树也是一种用于查找的平衡树，但是它不是二叉树。B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据与删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。这种数据结构常被应用在数据库和文件系统的实作上。B+树B+树是B树的变体，也是一种多路搜索树更适合文件索引系统和数据库。数据结构中的各种树4B+树典型结构5B*树是B+树的变体，在B+树的非根和非叶子节点再增加指向兄弟的指针，将节点的最低利用率从1/2提高到2/3。B*树分配新节点的概率比B+树要低，空间使用率更高。SQL Server的聚集索引和非聚集索引是B*树结构B*树如下图所示67PID:PID:816PID:1518PID:1860intermedia附件有B+树数据插入过程.gif8二分查找法又叫折半查找法举个栗子从10个数中查找48这个数5 10 19 21 31 3737 42 48 50 555 10 19 21 31 37 42 48 5050 555 10 19 21 31 37 42 4848 50 55只需要查找3次如果是顺序查找需要8次5 10 19 21 31 37 42 48489两种表页面组织结构聚集索引和非聚集索引都是B+树结构堆表+非聚集索引聚集索引+非聚集索引堆非聚集索引堆表聚集索引非聚集索引聚集索引表10堆表11498页面12分配扫描 VS 范围扫描13分配扫描 SELECT*FROM Departmentheap WHERE Name=销售部3 SELECT*FROM Departmentheap WHERE GroupName=销售组3 SELECT*FROM Departmentheap WHERE Company=中国你好有限公司XX分公司 SELECT*FROM Departmentheap WHERE ModifiedDate=2015-08-10 18:36:33 SELECT*FROM Departmentheap WHERE ModifiedDate=2015-08-10 18:36:33.220 AND Company=中国你好有限公司XX分公司 SELECT*FROM Departmentheap WHERE GroupName=销售组3 AND Name=销售部3 SELECT*FROM Departmentheap WHERE GroupName=销售组3 AND Name=销售部3 AND Company=中国你好有限公司XX分公司1415堆表+非聚集索引研究使用的命令：DBCC IND(库名,表名,格式)DBCC PAGE(库名,文件编号,页号,格式)其他研究工具:winhex使用示例：DBCC IND(pratice,Department8,-1)DBCC PAGE(pratice,1,255,3)16从DBCC IND命令可以看到非聚集索引有两层（index level）并且它会读取每个页面的页头 m_prevPage=(1:254)m_nextPage=(1:304)双向链表：order by1718root page-root pageDBCC PAGE(pratice,1,164,3)19child page-child pageDBCC PAGE(pratice,1,250,3)20什么是什么是HEAP RID(KEY)FileID:PageID:SlotNumber21HEAP RID(KEY)有啥用？有啥用？RID查找（查找（RID lookup）SELECT*FROM dbo.Department8 WHERE Name=销售部222KeyHashValue有啥用？有啥用？类似于下面类似于下面C#线程同步代码线程同步代码SELECT Name,GroupName FROM dbo.Department8 WITH(ROWLOCK)WHERE Name=销售部销售部1623include()包含性列索引包含性列索引msdn：可以将非键列包含在非聚集索引中，以避免超过当前索引大小的限制（最大：可以将非键列包含在非聚集索引中，以避免超过当前索引大小的限制（最大键列数为键列数为16，最大索引键大小为，最大索引键大小为900字节），数据库引擎计算索引键列数或索引键大字节），数据库引擎计算索引键列数或索引键大小时候，不考虑非键列小时候，不考虑非键列http:/ in place2、non update in place前转指针的存在导致消耗更多前转指针的存在导致消耗更多IOForwarding Pointer:FileID:PageID:SlotNumberForwarded Records:FileID:PageID:SlotNumber pageno：180pageno：26725查看前转指针记录数查看前转指针记录数SELECT*FROM sys.dm_db_index_physical_stats(db_id(),OBJECT_ID(Department8),NULL,NULL,NULL)26后转指针后转指针记录归位记录归位1、收缩数据文件、收缩数据文件2、alter table xx rebuild归回原位置Forwarded Records:FileID:PageID:SlotNumber pageno：180pageno：26727非聚集索引的查找和扫描过程非聚集索引的查找和扫描过程28堆表堆表+非聚集索引执行计划非聚集索引执行计划SELECT GroupName FROM dbo.Department8 WHERE name=销售部销售部22-索引查找索引查找SELECT GroupName FROM dbo.Department8 WHERE GroupName=销售组销售组10-索引扫描索引扫描SELECT GroupName FROM dbo.Department8 WHERE DepartmentID=66-全表扫描全表扫描 只扫堆只扫堆SELECT DepartmentID,ModifiedDate FROM dbo.Department8 WHERE name=销售部销售部8 -索引查找索引查找 RID查找查找SELECT*FROM dbo.Department8 WHERE GroupName=销售组销售组10 -索引扫描索引扫描 RID查找查找 29几个未解决的问题几个未解决的问题1、非聚集索引和复合索引的作用，把非聚集索引抽象为原表的缩水版2、页面物理位置会不会变3、索引的根页面编号从哪里来，还有堆的IAM页面从哪里来4、误删数据是否一定可以恢复305、万一系统表页面损坏怎么办，表字段表结构6、一条记录跨多个页面？7、CREATE TABLE TB1(ID INT,NAME CHAR(100)CREATE NONCLUSTER INDEX IDX ON TB1(ID)SELECT ID FROM TB1 ORDER BY ID 要加order by吗？316、一条记录跨多个页面？LOB 数据类型包括text、ntext、image、xml、varchar(max)、nvarchar(max)、varbinary(max)和 CLR 用户定义类型PageType：1：数据页面；2：索引页面；3：Lob_mixed_page；4：Lob_tree_page；10：IAM页面Blob row at:Page(1:3046835)Slot 0 Length:84 Type:5(LARGE_ROOT_YUKON)Blob Id:131661824 Level:0 MaxLinks:5 CurLinks:2Child 0 at Page(1:3046834)Slot 0 Size:8040 Offset:8040 Child 1 at Page(1:3046832)Slot 0 Size:7960 Offset:160003233另一个研究工具USE praticeSELECT TOP 10%lockres%AS FID:PID:RID,*FROM dbo.Department834聚集索引表+非聚集索引研究使用的命令：DBCC IND(库名,表名,格式)DBCC PAGE(库名,文件编号,页号,格式)IndexID为 1 的都是聚集索引页面PageType 分页类型：1：数据页面；2：索引页面；10：IAM页面IndexID 索引ID：0 代表堆,1 代表聚集索引,2-999 代表非聚集索引35从DBCC IND命令可以看到聚集索引有两层（index level）并且它会读取每个页面的页头 m_prevPage=(1:464)m_nextPage=(1:491)双向链表：order by36root page-root pageDBCC PAGE(pratice,1,489,3)37child page-child pageDBCC PAGE(pratice,1,491,3)383940建立非聚集索引建立非聚集索引CREATE NONCLUSTERED INDEX NCL_GroupName ON dbo.Department7(GroupName)41root page-root pageDBCC PAGE(pratice,1,1264,3)42child page-child pageDBCC PAGE(pratice,1,1262,3)43什么是什么是UNIQUIFIER（KEY）用以保证聚集索引键唯一44DepartmentID(key)有啥用？有啥用？键查找（键查找（KEY lookup）SELECT*FROM dbo.Department7 WHERE GroupName=销售组745非聚集索引聚集索引通过聚集索引键进行关联46聚集索引的查找和扫描过程聚集索引的查找和扫描过程47书签查找书签查找1、键查找、键查找2、RID查找查找48聚集索引表聚集索引表+非聚集索引执行计划非聚集索引执行计划SELECT*FROM dbo.Department7 WHERE DepartmentID=66-聚集索引查找聚集索引查找SELECT GroupName FROM dbo.Department7 WHERE GroupName=销售组销售组10-索引查找索引查找SELECT*FROM dbo.Department7 WHERE GroupName=销售组销售组10-索引查找索引查找 键查找键查找SELECT*FROM dbo.Department7 WHERE Company=中国你好有限公司中国你好有限公司XX分公司分公司-聚集索引扫描聚集索引扫描49聚集索引表聚集索引表+非聚集索引执行计划非聚集索引执行计划CREATE NONCLUSTERED INDEX NCL_GroupName ON dbo.Department7(GroupName)CREATE NONCLUSTERED INDEX NCL_Name ON dbo.Department7(Name)-非聚集索引合并联接非聚集索引合并联接SELECT Name,GroupNameFROM pratice.dbo.Department7 WITH(INDEX(NCL_Name,NCL_GroupName)WHERE Name=销售部销售部99 AND GroupName=销售组销售组9950
