请教下数据库索引文件存储结构 最近在读文章总是提数据库索引文件使用b数结构存储,我就疑问文件怎么可能存数据结构呢?我知道索引文件读到内存肯定是b树结构,那请问高手们是如何通过索引文件读取到内存变成b树结构的?数据库索引文件存的内容到底是什么呢?谢谢 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 b-tree结构指的是数据的逻辑存储方式。物理存储显然不会是指定顺序的存储,不然试想如果要update或者insert那需要多大的代价才能维护物理顺序啊。index(无论clustered或是non clustered)每一个leaf(叶节点)都有指向它的前项和后项,这样就维护了index的逻辑顺序。b-tree指的就是这个leaf链表形式的基础上,再建立它的上层(中间层和root,用于为它的leaf提供索引),好处是每一次lookup的消耗都是相同的(等于这个tree的depth)。index存了什么,如果是clustered index它存了这个表里所有的数据和key(用于lookup),如果是non clustered index它存了这个表的clustered index key(如果表没有clustered index,那就是RID,RID包括了fileid,pageid,slotid?,可以用于直接定位到需要的数据),如果这个nonclustered index有included column,这个数据也会被储存在index里。如果要进一步研究物理结构,那就更复杂了,推荐去读一下inside sql server - storage engine。看完以后(当然还要配合msdn的一些文章),lz就全清楚啦。纯手打,求给分~哈哈 内存(你指的是buffer pool吧)的作用无非是把物理磁盘的数据读进内存,避免反复I/O读写。你所谓的b树结构是逻辑结构。举个例子,比如index的page结构大致是这样的,File/Page ID: xxxIAMF/PID: xxxIndex ID: xxxIndex Level: 0(代表是leaf)PrevFile/Page ID: xxxNextFile/Page ID: xxx..还有其他一些信息保罗它里面每一个index row有了index level,它的前后file和page ID组成了树结构。index无论在磁盘还是内存里都是以这一个一个的页保存的。 对于b树逻辑结构我也理解,我想知道索引文件读入内存,文件内容里面存储的内容是什么?mysql通过如何将文件里面的内容解析成b树的逻辑结构?我的感觉文件内容里面放着id nextid preid等信息再次感谢mayuanf 哈哈,楼主这个问题真是难倒我们了,因为微软不告诉咱们他怎么按照B树写入文件:)而且不同的数据库,对于索引的存储结构也是不完全相同的比如SQL Server规定了,一个索引页就是固定的8KB而Oracle可以自定义索引页的大小,等等但是原理都是B树,这个是不会错的 内存里面存储的和索引在磁盘上存储过程结构相同,只是存储在内存里避免频繁磁盘IO节省时间。索引在磁盘上存储时也是按页存储的,如果单纯从物理结构上来说就是连续的存储页而已,而他们的逻辑结构是通过指针实现的b树,并不是在磁盘上或者内存上就是b树的结构了。b树只是逻辑上的,不是物理上的。其实mayuanf已经说得很明白了,只是索引空间与表空间的数据物理存储顺序有点不一样,还是有区别的。LZ不要太纠结了。LZ真想弄明白SQL Server在磁盘上怎么存储索引的可以看看TSQL技术内幕索引部分,给您个例子USE MASTERGOCREATE TABLE sp_table_pages( PagefID tinyint, PagePID int, IAMFID tinyint, IAMPID int, ObjectID int, IndexID tinyint, PartitionNumber tinyint, PartitionID bigint, iam_chain_type varchar(30), PageType tinyint, IndexLevel tinyint, NextPageFID tinyint, NextPagePID int, PrevPageFID tinyint, PrevPagePID int, Primary Key (PageFID,PagePID))TRUNCATE TABLE sp_table_pagesINSERT INTO sp_table_pages EXEC ('dbcc ind (AdventureWorks,[Sales.SalesOrderDetail],-1)')SELECT * FROM sp_table_pagesCREATE TABLE Clustered_Dupes( Col1 char(5) NOT NULL, Col2 int NOT NULL, Col3 CHAR(3) NULL, Col4 CHAR(6) NOT NULL)CREATE CLUSTERED INDEX Cl_dupes_col1 ON Clustered_Dupes(col1)GOSELECT first,indid,keycnt,name FROM sysindexesWHERE id = object_id('Clustered_Dupes')--查找索引中的第一个数据分页INSERT INTO Clustered_Dupes VALUES ('ABCDE',123,NULL,'CCCC')GOTRUNCATE TABLE sp_table_pagesGOINSERT INTO sp_table_pages EXEC ('DBCC IND(AdventureWorks,Clustered_Dupes,-1)')GOSELECT PageFID,PagePID FROM sp_table_pagesWHERE PageType = 1 and PrevPageFID = 0 and PrevPagePID = 0GO--查看分页内容--开启跟踪标记DBCC TRACEON(3604)GODBCC PAGE (AdventureWorks,1,20767,1)/*Row - Offset 0 (0x0) - 96 (0x60) DBCC 执行完毕。如果 DBCC 输出了错误信息,请与系统管理员联系。*/INSERT INTO Clustered_Dupes VALUES ('ABCDE',456,null,'DDDD')INSERT INTO Clustered_Dupes VALUES ('ABCDE',64,null,'EEEE')--查看数据页面内容DBCC PAGE(AdventureWorks,1,20767,1)/*OFFSET TABLE:Row - Offset 2 (0x2) - 154 (0x9a) 1 (0x1) - 121 (0x79) 0 (0x0) - 96 (0x60) DBCC 执行完毕。如果 DBCC 输出了错误信息,请与系统管理员联系。*/--显示聚集索引结点行的结构CREATE TABLE Clustered_nodupes( id int NOT NULL, str1 char(5) NOT NULL, str2 char(600) NULL)GOCREATE CLUSTERED INDEX idxCL ON Clustered_Nodupes (str1)GOSET NOCOUNT ONGODECLARE @i intSET @i = 1024WHILE @i < 13000 BEGIN INSERT INTO Clustered_Nodupes SELECT @i,CAST(@i AS CHAR),CAST(@i AS CHAR) SET @i = @i + 1ENDGOTRUNCATE TABLE sp_table_pagesINSERT INTO sp_table_pages EXEC ('DBCC IND (AdventureWorks,Clustered_Nodupes,-1)')SELECT PageFID,PagePID,IndexLevel,PageType FROM sp_table_pagesWHERE IndexId = 1 and IndexLevel >= 0 and PrevPageFId = 0 and PrevPagePID = 0--结果/*PageFID PagePID IndexLevel PageType1 20970 0 11 20972 1 21 21554 2 2*/--查看数据页内容DBCC PAGE (AdventureWorks,1,20970,1).........Row - Offset 79 (0x4f) - 144 (0x90) 78 (0x4e) - 4008 (0xfa8) 77 (0x4d) - 4020 (0xfb4) 76 (0x4c) - 3996 (0xf9c) 75 (0x4b) - 3984 (0xf90) 74 (0x4a) - 3972 (0xf84) 73 (0x49) - 3960 (0xf78) 72 (0x48) - 3948 (0xf6c) 71 (0x47) - 3864 (0xf18) 70 (0x46) - 3924 (0xf54) 69 (0x45) - 3936 (0xf60) 68 (0x44) - 3912 (0xf48) 67 (0x43) - 3900 (0xf3c) 66 (0x42) - 3888 (0xf30) 65 (0x41) - 3876 (0xf24) 64 (0x40) - 132 (0x84) 63 (0x3f) - 3840 (0xf00) 62 (0x3e) - 3852 (0xf0c) 61 (0x3d) - 3828 (0xef4) 60 (0x3c) - 3816 (0xee8) 59 (0x3b) - 3804 (0xedc) 58 (0x3a) - 3792 (0xed0) 57 (0x39) - 3780 (0xec4) 56 (0x38) - 3696 (0xe70) 55 (0x37) - 3756 (0xeac) 54 (0x36) - 3768 (0xeb8) 53 (0x35) - 3744 (0xea0) 52 (0x34) - 3732 (0xe94) 51 (0x33) - 3720 (0xe88) 50 (0x32) - 3708 (0xe7c) 49 (0x31) - 120 (0x78) 48 (0x30) - 3672 (0xe58) 47 (0x2f) - 3684 (0xe64) 46 (0x2e) - 3660 (0xe4c) 45 (0x2d) - 3648 (0xe40) 44 (0x2c) - 3636 (0xe34) 43 (0x2b) - 3624 (0xe28) 42 (0x2a) - 3612 (0xe1c) 41 (0x29) - 3528 (0xdc8) 40 (0x28) - 3588 (0xe04) 39 (0x27) - 3600 (0xe10) 38 (0x26) - 3576 (0xdf8) 37 (0x25) - 3564 (0xdec) 36 (0x24) - 3552 (0xde0) 35 (0x23) - 3540 (0xdd4) 34 (0x22) - 108 (0x6c) 33 (0x21) - 3504 (0xdb0) 32 (0x20) - 3516 (0xdbc) 31 (0x1f) - 3492 (0xda4) 30 (0x1e) - 3480 (0xd98) 29 (0x1d) - 3468 (0xd8c) 28 (0x1c) - 3456 (0xd80) 27 (0x1b) - 3444 (0xd74) 26 (0x1a) - 3132 (0xc3c) 25 (0x19) - 3420 (0xd5c) 24 (0x18) - 3432 (0xd68) 23 (0x17) - 3408 (0xd50) 22 (0x16) - 3396 (0xd44) 21 (0x15) - 3384 (0xd38) 20 (0x14) - 3372 (0xd2c) 19 (0x13) - 3144 (0xc48) 18 (0x12) - 3360 (0xd20) 17 (0x11) - 3348 (0xd14) 16 (0x10) - 3336 (0xd08) 15 (0xf) - 3324 (0xcfc) 14 (0xe) - 3312 (0xcf0) 13 (0xd) - 3300 (0xce4) 12 (0xc) - 3288 (0xcd8) 11 (0xb) - 3276 (0xccc) 10 (0xa) - 3264 (0xcc0) 9 (0x9) - 3252 (0xcb4) 8 (0x8) - 3240 (0xca8) 7 (0x7) - 3228 (0xc9c) 6 (0x6) - 3216 (0xc90) 5 (0x5) - 3204 (0xc84) 4 (0x4) - 3192 (0xc78) 3 (0x3) - 3180 (0xc6c) 2 (0x2) - 3168 (0xc60) 1 (0x1) - 3156 (0xc54) 0 (0x0) - 96 (0x60) /*看看加索引后根节点及offset的规律自己体会下吧,这个想搞明白不太容易的说。 日志文件有什么用?是不是记录着每一句的SQL? 请教这条sql语句等同于linq语句是什么、、、 望高手给一SQl语句,万分感谢!! 2005无法用DAC模式登陆!!! 急求SQL Server2005的两个数据库同步 SQL取得ACCESS表的结构 数据库附加不进去,急求答案。谢谢各位大牛 VC应用程序连接数据库 请问groupby的问题 Sql语句问题 sql默认约束 请教一个表设计的问题
举个例子,比如index的page结构大致是这样的,
File/Page ID: xxx
IAMF/PID: xxx
Index ID: xxx
Index Level: 0(代表是leaf)
PrevFile/Page ID: xxx
NextFile/Page ID: xxx
..还有其他一些信息保罗它里面每一个index row
有了index level,它的前后file和page ID组成了树结构。index无论在磁盘还是内存里都是以这一个一个的页保存的。
mysql通过如何将文件里面的内容解析成b树的逻辑结构?
我的感觉文件内容里面放着
id nextid preid等信息
再次感谢mayuanf
而且不同的数据库,对于索引的存储结构也是不完全相同的
比如SQL Server规定了,一个索引页就是固定的8KB而Oracle可以自定义索引页的大小,等等
但是原理都是B树,这个是不会错的
索引在磁盘上存储时也是按页存储的,如果单纯从物理结构上来说就是连续的存储页而已,而他们的逻辑结构是通过指针实现的b树,并不是在磁盘上或者内存上就是b树的结构了。b树只是逻辑上的,不是物理上的。其实mayuanf已经说得很明白了,只是索引空间与表空间的数据物理存储顺序有点不一样,还是有区别的。LZ不要太纠结了。LZ真想弄明白SQL Server在磁盘上怎么存储索引的可以看看TSQL技术内幕索引部分,给您个例子USE MASTER
GO
CREATE TABLE sp_table_pages
(
PagefID tinyint,
PagePID int,
IAMFID tinyint,
IAMPID int,
ObjectID int,
IndexID tinyint,
PartitionNumber tinyint,
PartitionID bigint,
iam_chain_type varchar(30),
PageType tinyint,
IndexLevel tinyint,
NextPageFID tinyint,
NextPagePID int,
PrevPageFID tinyint,
PrevPagePID int,
Primary Key (PageFID,PagePID)
)TRUNCATE TABLE sp_table_pages
INSERT INTO sp_table_pages EXEC ('dbcc ind (AdventureWorks,[Sales.SalesOrderDetail],-1)')SELECT * FROM sp_table_pagesCREATE TABLE Clustered_Dupes
(
Col1 char(5) NOT NULL,
Col2 int NOT NULL,
Col3 CHAR(3) NULL,
Col4 CHAR(6) NOT NULL
)CREATE CLUSTERED INDEX Cl_dupes_col1 ON Clustered_Dupes(col1)
GOSELECT first,indid,keycnt,name FROM sysindexes
WHERE id = object_id('Clustered_Dupes')--查找索引中的第一个数据分页
INSERT INTO Clustered_Dupes VALUES ('ABCDE',123,NULL,'CCCC')
GO
TRUNCATE TABLE sp_table_pages
GO
INSERT INTO sp_table_pages EXEC ('DBCC IND(AdventureWorks,Clustered_Dupes,-1)')
GO
SELECT PageFID,PagePID
FROM sp_table_pages
WHERE PageType = 1 and PrevPageFID = 0 and PrevPagePID = 0
GO--查看分页内容
--开启跟踪标记
DBCC TRACEON(3604)
GO
DBCC PAGE (AdventureWorks,1,20767,1)/*
Row - Offset
0 (0x0) - 96 (0x60)
DBCC 执行完毕。如果 DBCC 输出了错误信息,请与系统管理员联系。*/INSERT INTO Clustered_Dupes VALUES ('ABCDE',456,null,'DDDD')
INSERT INTO Clustered_Dupes VALUES ('ABCDE',64,null,'EEEE')--查看数据页面内容
DBCC PAGE(AdventureWorks,1,20767,1)/*
OFFSET TABLE:Row - Offset
2 (0x2) - 154 (0x9a)
1 (0x1) - 121 (0x79)
0 (0x0) - 96 (0x60)
DBCC 执行完毕。如果 DBCC 输出了错误信息,请与系统管理员联系。*/--显示聚集索引结点行的结构
CREATE TABLE Clustered_nodupes
(
id int NOT NULL,
str1 char(5) NOT NULL,
str2 char(600) NULL
)
GO
CREATE CLUSTERED INDEX idxCL ON Clustered_Nodupes (str1)
GO
SET NOCOUNT ON
GO
DECLARE @i int
SET @i = 1024
WHILE @i < 13000
BEGIN
INSERT INTO Clustered_Nodupes
SELECT @i,CAST(@i AS CHAR),CAST(@i AS CHAR)
SET @i = @i + 1
END
GOTRUNCATE TABLE sp_table_pages
INSERT INTO sp_table_pages EXEC ('DBCC IND (AdventureWorks,Clustered_Nodupes,-1)')
SELECT PageFID,PagePID,IndexLevel,PageType
FROM sp_table_pages
WHERE IndexId = 1 and IndexLevel >= 0 and PrevPageFId = 0 and PrevPagePID = 0--结果
/*
PageFID PagePID IndexLevel PageType
1 20970 0 1
1 20972 1 2
1 21554 2 2
*/--查看数据页内容
DBCC PAGE (AdventureWorks,1,20970,1).........
Row - Offset
79 (0x4f) - 144 (0x90)
78 (0x4e) - 4008 (0xfa8)
77 (0x4d) - 4020 (0xfb4)
76 (0x4c) - 3996 (0xf9c)
75 (0x4b) - 3984 (0xf90)
74 (0x4a) - 3972 (0xf84)
73 (0x49) - 3960 (0xf78)
72 (0x48) - 3948 (0xf6c)
71 (0x47) - 3864 (0xf18)
70 (0x46) - 3924 (0xf54)
69 (0x45) - 3936 (0xf60)
68 (0x44) - 3912 (0xf48)
67 (0x43) - 3900 (0xf3c)
66 (0x42) - 3888 (0xf30)
65 (0x41) - 3876 (0xf24)
64 (0x40) - 132 (0x84)
63 (0x3f) - 3840 (0xf00)
62 (0x3e) - 3852 (0xf0c)
61 (0x3d) - 3828 (0xef4)
60 (0x3c) - 3816 (0xee8)
59 (0x3b) - 3804 (0xedc)
58 (0x3a) - 3792 (0xed0)
57 (0x39) - 3780 (0xec4)
56 (0x38) - 3696 (0xe70)
55 (0x37) - 3756 (0xeac)
54 (0x36) - 3768 (0xeb8)
53 (0x35) - 3744 (0xea0)
52 (0x34) - 3732 (0xe94)
51 (0x33) - 3720 (0xe88)
50 (0x32) - 3708 (0xe7c)
49 (0x31) - 120 (0x78)
48 (0x30) - 3672 (0xe58)
47 (0x2f) - 3684 (0xe64)
46 (0x2e) - 3660 (0xe4c)
45 (0x2d) - 3648 (0xe40)
44 (0x2c) - 3636 (0xe34)
43 (0x2b) - 3624 (0xe28)
42 (0x2a) - 3612 (0xe1c)
41 (0x29) - 3528 (0xdc8)
40 (0x28) - 3588 (0xe04)
39 (0x27) - 3600 (0xe10)
38 (0x26) - 3576 (0xdf8)
37 (0x25) - 3564 (0xdec)
36 (0x24) - 3552 (0xde0)
35 (0x23) - 3540 (0xdd4)
34 (0x22) - 108 (0x6c)
33 (0x21) - 3504 (0xdb0)
32 (0x20) - 3516 (0xdbc)
31 (0x1f) - 3492 (0xda4)
30 (0x1e) - 3480 (0xd98)
29 (0x1d) - 3468 (0xd8c)
28 (0x1c) - 3456 (0xd80)
27 (0x1b) - 3444 (0xd74)
26 (0x1a) - 3132 (0xc3c)
25 (0x19) - 3420 (0xd5c)
24 (0x18) - 3432 (0xd68)
23 (0x17) - 3408 (0xd50)
22 (0x16) - 3396 (0xd44)
21 (0x15) - 3384 (0xd38)
20 (0x14) - 3372 (0xd2c)
19 (0x13) - 3144 (0xc48)
18 (0x12) - 3360 (0xd20)
17 (0x11) - 3348 (0xd14)
16 (0x10) - 3336 (0xd08)
15 (0xf) - 3324 (0xcfc)
14 (0xe) - 3312 (0xcf0)
13 (0xd) - 3300 (0xce4)
12 (0xc) - 3288 (0xcd8)
11 (0xb) - 3276 (0xccc)
10 (0xa) - 3264 (0xcc0)
9 (0x9) - 3252 (0xcb4)
8 (0x8) - 3240 (0xca8)
7 (0x7) - 3228 (0xc9c)
6 (0x6) - 3216 (0xc90)
5 (0x5) - 3204 (0xc84)
4 (0x4) - 3192 (0xc78)
3 (0x3) - 3180 (0xc6c)
2 (0x2) - 3168 (0xc60)
1 (0x1) - 3156 (0xc54)
0 (0x0) - 96 (0x60)
/*
看看加索引后根节点及offset的规律自己体会下吧,这个想搞明白不太容易的说。