B树索引是怎么样利用在硬盘上的

.Net技术 码拜 5年前 (2016-06-08) 1185次浏览
假设B树存储的是索引的键,以及键所对应的内容的硬盘上存储地址。
那么问题来了。
1.索引往往都是很大的,往往都存在硬盘上。本人不可能一次性都读取出来。然后在内存中来进行查找比对,然后再到硬盘对应的位置把数据取出来。这样本人还用B树来构建索引干鸟。那数据库索引是怎么工作的呢?
2.基于问题1。假设B树不但存储了索引的键,还有对应内容的地址,他还存储了他的孩子节点的地址。那么我们可以每次只读取一个节点,然后进行比较。假如没找到,则根据条件跳到下一个节点继续查找。这样没问题,但是这个索引文件我们怎么样构造?一个个节点的地址怎么样生成?又怎么样通过程序根据这些地址去获取到数据?最后又怎么样将一个个节点的内容保存起来生成一个索引文件?
简单的来说,本人就是想本人构建一个非常微型的数据库。关于数据库索引的文章非常多,也有很多结合了硬盘来说。但都非常不全面,没有说到具体怎么去在硬盘上构建索引,以及利用索引在硬盘上进行查找。希望大家帮忙解答下本人心中的疑问,本人非常苦恼这个问题。
有学习材料更好。语言最好是C++或C#的。
解决方案

50

1. 索引即可能全都读取到内存,也可能不全部读取到内存,不同数据库系统的实现有所不同。
索引并不大,所以把单个索引一次性地读入内存也是可以的。例如一个数据表可能有100M 空间,其索引可能只占用200K。除非你是把一条记录里边几乎全部字段都组合起来作为索引键,否则怎么可能索引跟数据的大小相似呢?
假设数据库有100个表、200个索引,不必一次把全部索引都读入内存,用到哪一个再读哪一个。相似地,你也可以在读取索引时仅仅读取其顶层对象在内存中创建映射,而将下一级的节点使用一个自定义的 Lazy 机制对象(也就是说比普通对象来说,多一个判断能否“有值”的功能和一个“加载”功能),需要扩展哪一个节点时才读取某个节点的下一层节点。
从性能上说,读取整个(单个的)索引到内存里是性能和功能很好的平衡。动态加载节点则有可能过于谨慎。

50

2. 这个问题,在任何一本关于数据库原理的教科书上都有。注意本人说的是“数据库原理”,而许多人学过的可能只是简单应用(也就是职业教育的入门教程,而非针对从事研发工作的人的教程)。
你找一个数据库原理方面的书,它会告诉你通用的关系数据库系统怎么样设计本人的虚拟数据块(书上可能翻译为“虚拟磁盘块”),数据块列表(使用中的、空闲的),例如每块1M大小。
一个文件内部,可以包括多个虚拟数据块。每一块都有一个指针链接到下一块。同时文件头部可以有几十字节固定区域,用来定义诸如“链表1、链表2、链表3、链表4的起始偏移”,以及“最大链表长度、多少分钟压缩合并一次空闲”等等全局设置。
每一数据块中保存多条记录,因此每一个记录的“地址”其实就是“文件内磁盘块地址+磁盘块内数据数组下标”。
当数据被创建时,可以插入“某个正在使用的”磁盘块的空闲空间中(同时原因是块内空闲空间的),假如没有则从空闲磁盘块列表上取下一个磁盘块使用,假如还没有则动态扩大文件(例如1M空间)来分配一个磁盘块使用。
当数据删除时,它可以挪动磁盘块内的空间(使得空闲部分集中到尾部)。假如数据原来是磁盘块中唯一一个,则磁盘块变为空闲。假如数据不是原来磁盘块中唯一一条数据,则磁盘块在“使用中的磁盘块”的链表的位置可能原因是空闲增大而向前移动。
所以,一个普通的可随机读写的文件,囊括了数据库系统全部数据。而并不需要分成许多文件。
数据的“所在数据块编号”不一定是绝对对应于文件中的偏移地址,完全可以在数据库系统初始化时一次性扫描全部数据块,在内存中创建字典数据结构。假如说单个索引可以不一次性读入内存,但是这个数据块编号跟数据块的文件偏移地址的对应关系,则一定要一次性读入内存的。

20

引用:

简单的来说,本人就是想本人构建一个非常微型的数据库。关于数据库索引的文章非常多,也有很多结合了硬盘来说。但都非常不全面,没有说到具体怎么去在硬盘上构建索引,以及利用索引在硬盘上进行查找。

事实上,假如你是开发一个“微型”的数据库,那么你完全可以在运行时、系统初始化时才临时创建索引,在系统关闭之前将索引序列化到磁盘(例如文件头部的“链表4”来记录顺序记录序列化了得索引数组的起始地址)。假设关闭之前若没有正确保存索引,则下次初始化启动时则重建索引,否则就读取上次保存的值在内存中反序列化。对索引可以稍微简单粗暴地处理。

80

文件在硬盘中是以族为单位存储的,所以你在组织树节点数据时最好不要超过族的规模
这样读取时就是最快的

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明B树索引是怎么样利用在硬盘上的
喜欢 (0)
[1034331897@qq.com]
分享 (0)