SQLSERVER中KeyHashValue的作用（上） SQLSERVER中KeyHashValue的作用（下） 原文的标题是：SQLSERVER在索引下如何找到哈希值的随想 现在知道KeyHashValue的作用了，所以就改了标题~ 测试环境：SQLSERVER2005 开发者版 真的不好意思，我做实验的时候到最后还
SQLSERVER中KeyHashValue的作用（上）
SQLSERVER中KeyHashValue的作用（下）
原文的标题是：SQLSERVER在索引下如何找到哈希值的随想
现在知道KeyHashValue的作用了，所以就改了标题~
测试环境：SQLSERVER2005 开发者版
真的不好意思，我做实验的时候到最后还是没有找到这个问题的答案
问题是这样的：
当通过聚集索引查找和非聚集索引查找的时候，通过哈希码来匹配，然后找到相应记录的
既然通过哈希码来匹配，那么就需要一个hash bucket把所有索引页面的所有key/value全部加载到hash bucket
既然要全部加载到hash bucket就需要读取所有的索引页
我的测试脚本，我使用SET STATISTICS IO ON来测试是否有读取索引页的情况，但是到最后还是找不到规律
1 -- sql在聚集索引下如何找到哈希值的随想
2
3 USE master
4 GO
5 -- 新建数据库IAMDB
6 CREATE DATABASE SCANDB
7 GO
8
9 USE SCANDB
10 GO
11
12
13
14 -- DROP TABLE clusteredtable
15 -- DROP TABLE nonclusteredtable
16
17
18 -- 建立测试表
19 CREATE TABLE clusteredtable(c1 INT IDENTITY ( 1 , 1 ), c2 VARCHAR ( 900 ))
20 GO
21 CREATE TABLE nonclusteredtable(c1 INT IDENTITY ( 1 , 1 ), c2 VARCHAR ( 900 ))
22 GO
23
24
25 -- 建立索引
26 CREATE CLUSTERED INDEX cix_clusteredtable ON clusteredtable( [ C2 ] )
27 GO
28 CREATE INDEX ix_nonclusteredtable ON nonclusteredtable( [ C2 ] )
29 GO
30
31
32 -- 插入测试数据
33 DECLARE @a INT ;
34 SELECT @a = 1 ;
35 WHILE ( @a 100 )
36 BEGIN
37 INSERT INTO clusteredtable VALUES ( CAST ( @a AS NVARCHAR ( 2 )) + replicate ( ' a ' , 880 ))
38 SELECT @a = @a + 1
39 END
40
41
42 DECLARE @a INT ;
43 SELECT @a = 1 ;
44 WHILE ( @a 100 )
45 BEGIN
46 INSERT INTO nonclusteredtable VALUES ( CAST ( @a AS NVARCHAR ( 2 )) + replicate ( ' a ' , 880 ))
47 SELECT @a = @a + 1
48 END
49
50
51
52
53 -- 查询数据
54 SELECT * FROM clusteredtable ORDER BY [ c1 ] ASC
55 SELECT * FROM nonclusteredtable ORDER BY [ c1 ] ASC
56
57
58 CREATE TABLE DBCCResult (
59 PageFID NVARCHAR ( 200 ),
60 PagePID NVARCHAR ( 200 ),
61 IAMFID NVARCHAR ( 200 ),
62 IAMPID NVARCHAR ( 200 ),
63 ObjectID NVARCHAR ( 200 ),
64 IndexID NVARCHAR ( 200 ),
65 PartitionNumber NVARCHAR ( 200 ),
66 PartitionID NVARCHAR ( 200 ),
67 iam_chain_type NVARCHAR ( 200 ),
68 PageType NVARCHAR ( 200 ),
69 IndexLevel NVARCHAR ( 200 ),
70 NextPageFID NVARCHAR ( 200 ),
71 NextPagePID NVARCHAR ( 200 ),
72 PrevPageFID NVARCHAR ( 200 ),
73 PrevPagePID NVARCHAR ( 200 )
74 )
75
76 TRUNCATE TABLE [ dbo ] . [ DBCCResult ]
77
78 INSERT INTO DBCCResult EXEC ( ' DBCC IND(SCANDB,nonclusteredtable,-1) ' )
79
80 SELECT * FROM [ dbo ] . [ DBCCResult ] ORDER BY [ PageType ] DESC
81
82 DBCC TRACEON( 3604 , - 1 )
83 GO
84 DBCC PAGE(SCANDB, 1 , 89 , 3 )
85 GO
86
87 checkpoint
88 DBCC DROPCLEANBUFFERS
89 DBCC freesystemcache( ' all ' )
90 GO
91 -- ---------------------------------
92 SET STATISTICS IO ON
93 GO
94 -- 聚集索引查找
95 SELECT * FROM clusteredtable WHERE [ c2 ] = ' 18aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa '
96 SET STATISTICS IO OFF
97 GO
98
99
100
101 ( 1 行受影响)
102 表 ' clusteredtable ' 。扫描计数 1 ，逻辑读取 4 次，物理读取 2 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
103
104
105
106
107 -- --------------------------------------------------------------------------------------
108 checkpoint
109 DBCC DROPCLEANBUFFERS
110 DBCC freesystemcache( ' all ' )
111 GO
112 -- ---------------------------------
113 SET STATISTICS IO ON
114 GO
115 -- 索引查找 、RID查找 、嵌套循环
116 SELECT * FROM nonclusteredtable WHERE [ c2 ] = ' 17aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa '
117 SET STATISTICS IO OFF
118 GO
119
120
121
122 ( 1 行受影响)
123 表 ' nonclusteredtable ' 。扫描计数 1 ，逻辑读取 5 次，物理读取 1 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
View Code
聚集索引表的情况
非聚集索引表的情况
今天中午跟高文佳兄讨论了很长时间，我把关键讨论部分贴出来，大家参考参考，讨论的最后结果是：还没有解释到keyhashvalue字段实际的作用
感谢高文佳，头脑非常灵活
ō笑东风ō 9:27:10
对了 你那个hash的问题
ō笑东风ō 9:27:21
感觉你研究的方向不对
ō笑东风ō 9:28:05
当通过聚集索引查找和非聚集索引查找的时候，通过哈希码来匹配，然后找到相应记录的
桦少 9:28:53
请指教
ō笑东风ō 9:29:00
查找时不会使用hash来查找 因为hash值没有排序 无法最快查找
桦少 9:29:18
ō笑东风ō 9:29:20 应该是按照key来查找
桦少 9:33:52
ō笑东风ō 9:29:20
应该是按照key来查找
桦少 9:33:55
说说你的思路
ō笑东风ō 9:34:18
在索引里已经按照KEY排序 对吧
ō笑东风ō 9:34:34
而按照key排序 能最快找到想要的值
桦少 9:35:38
key排序有争议
桦少 9:35:42
又怎样
桦少 9:35:58
你还没有说清楚
ō笑东风ō 9:37:21
先说key查找的
我记得你有篇blog里说过hashjoin
桦少 9:39:38
哪三个经典连接没有写
ō笑东风ō 9:40:56
反正我的观点是key查找最快 无须再使用hash来定位
ō笑东风ō 9:41:26
而只有在hash join才会用到hash
笑东风ō 9:40:56
反正我的观点是key查找最快 无须再使用hash来定位
而只有在hash join才会用到hash
桦少 12:50:35
你想好啦吗
ō笑东风ō 12:51:57
嗯 我还是认为聚簇索引和非聚簇索引只存在key lookup
桦少 12:55:46
key lookup
的原理是什么
桦少 12:55:52
操作步骤是怎样的
桦少 12:55:56
你知道吗
ō笑东风ō 12:59:31
就是平衡树的原理
桦少 13:00:31
好
ō笑东风ō 13:00:38
使用平衡树 对上百万的INT值进行查找只需要4步
桦少 13:00:58
你查找的时候是否需要从磁盘读取索引页面到内存
ō笑东风ō 13:01:05
对
桦少 13:01:06
先不说他用多少步
桦少 13:01:08
性能有多好
桦少 13:01:26
从磁盘读取整个表的索引页面到内存
桦少 13:01:29
整个表
桦少 13:01:41
然后构成你说的所谓的平衡树
桦少 13:01:46
对吧
ō笑东风ō 13:02:06
对
桦少 13:02:52
我的问题就是这个
桦少 13:03:01
我用statictis io
桦少 13:03:10
看不出他会读取所有的索引页面
ō笑东风ō 13:04:25
一次seek 当然不会读取所有的页面
ō笑东风ō 13:04:48
只有scan才会读取所有页面
桦少 13:05:36
你还是不明白我问的问题
桦少 13:06:18
我说的是索引页
桦少 13:06:26
不是数据页
ō笑东风ō 13:06:45
索引也一样
ō笑东风ō 13:06:50
等等我给你做个demo
桦少 13:08:00
还有 ō笑东风ō 13:08:30
我现在有[BackupTestDB].[dbo].[TB1] 表中数据有245461条
桦少 13:08:43
你说用二叉树
ō笑东风ō 13:08:44
桦少 13:08:47
如果是这样
桦少 13:08:59
那么，keyhashvalue就没有意义了
ō笑东风ō 13:09:06
不是二叉树 是B树
桦少 13:09:15
桦少 13:09:23
b树 桦少 13:09:51
所以我从hash bucket的角度去思考
ō笑东风ō 13:10:22
hash桶这个概念是为了HASH JOIN才产生的
桦少 13:10:36
如果用b树，从第一个最左边的叶子节点开始从磁盘读取索引页面，组装一棵B树
ō笑东风ō 13:11:05
继续
桦少 13:11:23
如果是这样，keyhashvalue这个字段根本不需要
桦少 13:12:12
用到key alue的都可以用桶这个概念啊
桦少 13:12:19
我觉得
桦少 13:12:47
我觉得不用死磕书本
桦少 13:13:06
死磕书本等于读死书
ō笑东风ō 13:14:28
桦少 13:14:49
桦少 13:15:58
我以前做实验的时候也看到过keyhashvalue全部为null
桦少 13:16:47
想写在SQLSERVER聚集索引与非聚集索引的再次研究（上）文章的最后面的
桦少 13:16:58
但是因为解释不了这个现象
桦少 13:17:01
最后没有写
桦少 13:19:42
为什麽我提出这个想法
桦少 13:19:52
其实我也是从性能和速度考虑的
ō笑东风ō 13:20:09
骚等
桦少 13:20:21
我的想法是：sqlserver有可能不用你刚才说的B树来找记录
ō笑东风ō 13:20:31
我怀疑这个HASHvalus是为了在seek时做比较用的
桦少 13:20:45
我画图给你看
桦少 13:22:42
当我用聚集索引查找的时候
桦少 13:23:11
key的字段是id
桦少 13:23:25
表中的字段是id
桦少 13:23:32
id是聚集索引字段
桦少 13:23:50
value是数据页面号
桦少 13:24:12
我要找id为9的那条记录
桦少 13:24:58
等一下
桦少 13:25:02
图还没画好
桦少 13:26:27
桦少 13:26:51
我需要将索引页69，88，102读取到内存
桦少 13:26:57
构成一棵b树
桦少 13:27:13
从左到右，从上到下查找
桦少 13:27:30
直至找到key为9那条记录
桦少 13:27:59
如果我select的是id为3的那条记录
桦少 13:28:17
我就不用读取索引页88，102读取到内存
桦少 13:28:23
只需要读取索引页面69
桦少 13:30:29
改一下，数据页面编号没有英文字母的
桦少 13:30:30
桦少 13:30:37
睡醒再聊
桦少 14:05:59
当我找id为9的记录的时候
桦少 14:06:16
我需要扫描索引页面69和索引页面88
ō笑东风ō 14:06:28
不需要扫面69
ō笑东风ō 14:06:42
只需要扫描88和102
桦少 14:06:43
说错了
桦少 14:06:54
是的
桦少 14:07:15
但是你也需要从磁盘读取索引页面69吧
桦少 14:07:22
组装出一棵b树
桦少 14:08:56
逐行逐行扫描 索引页面88和102里的记录
桦少 14:09:08
直到扫描到id为9的那条记录才停止
桦少 14:09:14
我的想法是
桦少 14:09:51
我的想法是：sqlserver有可能不用你刚才说的B树来找记录
ō笑东风ō 14:09:53
页面内扫描是这样
桦少 14:10:59
将所有索引页面的key列和value列放进去hash桶
桦少 14:11:07
ō笑东风ō 14:11:31
我刚在我本地跑了下你的脚本 SQL SERVER 2008 SP2
桦少 14:11:32
通过算法查找到id为9的那一条记录
ō笑东风ō 14:11:38
没有hashkey
ō笑东风ō 14:11:59
你的平台是什么
桦少 14:12:04
这样就不用扫描：索引页面88和102里的记录
桦少 14:12:32
桦少 14:12:39 但是他就不用扫描
桦少 14:12:47 sql2005
ō笑东风ō 14:13:14
我到时有一种猜测
桦少 14:13:57
不然无办法解释keyhashvalue这个字段
ō笑东风ō 14:14:07
当比如较大字符串的时候 如果将字符串先hash后比较hash值 如果hash值相同 在比较字符串 这样效率会高一些
桦少 14:16:54
这种方法有一个缺点
ō笑东风ō 14:17:17
什么缺点
桦少 14:18:10
如果我select的是id为3的那条记录 他都会把所有索引页面读取到内存
桦少 14:18:20
而不像B树
桦少 14:18:36
桦少 14:18:43
因为他需要在桶里面找
ō笑东风ō 14:19:53
如果按照你所想的这样 无法快读定位某一个值的行
ō笑东风ō 14:20:03
必须扫描所有页
ō笑东风ō 14:20:17
除非对hashvalue进行排序
桦少 14:21:01
扫描所有索引页面
桦少 14:21:20
把所有索引页面里的keyhashvalue读取到桶里面
桦少 14:21:22
然后查找
ō笑东风ō 14:26:27
而且到hash桶后 还需要排序 如果不排序 需要全部遍历
桦少 14:27:33
嗯嗯
桦少 14:27:43
所以我的文章标题是：随想
ō笑东风ō 14:29:36
我知道有一种程序设计 是这样做的 就是对大字段做hash 然后对hash作为一列存储 对hash列建立索引
ō笑东风ō 14:30:04
这样做等值查询时能提高查询效率
桦少 14:32:58
高兄你是不是想偏了
桦少 14:33:09
不是只有大字段才有hash
ō笑东风ō 14:33:38
我只是说这是一种设计思路
桦少 14:33:39
ō笑东风ō 14:34:14
任何数据都可以被hash
桦少 14:34:37
不过这里好像说不过去
ō笑东风ō 14:36:10
而且林兄你看到的这些都是非叶子节点哈
桦少 14:50:22
当然是非叶子节点啦
桦少 14:50:33
叶子节点就是数据页面
ō笑东风ō 14:51:28
这个hashvalue应该跟seek无关
桦少 14:52:39
所以我才说无办法解释嘛
ō笑东风ō 14:59:25
嗯嗯
查看更多关于SQLSERVER中KeyHashValue的作用（上）的详细内容...