数据结构 – 为什么我们需要一个单独的数据结构,如数据库和文件

发布时间：2020-12-12 08:41:08 所属栏目：MsSql教程来源：网络整理

导读：我在B树上阅读,看起来像在O(lg n)时间内实现动态集合操作.红黑树( JavaMap中的TreeMap)也在渐近的同一时间框架内实现了相同的操作.所以我想知道什么使B树对数据库和文件系统更有用解决方法存在B-tree的主要原因是更好地利用读取和写入大块数据的设备的行为.

我在B树上阅读,看起来像在O(lg n)时间内实现动态集合操作.红黑树( JavaMap中的TreeMap)也在渐近的同一时间框架内实现了相同的操作.所以我想知道什么使B树对数据库和文件系统更有用

存在B-tree的主要原因是更好地利用读取和写入大块数据的设备的行为.当数据必须存储在磁盘上时,两个属性对于使B-Tree比二叉树更好：

>访问磁盘真的很慢(与内存或缓存相比,对磁盘上的数据的随机访问数量级更慢);和
>每次读取都会导致整个扇区从驱动器加载 – 假设扇区大小为4K,这意味着1000个整数,或者您正在存储的数十个较大的对象.

因此,我们可以利用第二个事实的优点,同时最大限度地减少磁盘访问的次数.

所以,我们可以创建一个更大的索引来告诉我们,如果我们应该继续到第一个1/100,再到第二个或第99页(想象图书馆按照他们的第一个字母排序,然后是第二个,依此类推).只要所有这些数据都适合单个部门,它将被加载,所以我们可以完全使用它.

这导致大致logB N查找,其中N是记录数.这个数字虽然与log2 N相同,但实际上与N和b足够小几倍,而且由于我们正在谈论将数据存储到磁盘中以用于数据库等,数据量通常很大足以证明这一点.

设计决策的其余部分主要是为了使这个工作有效地工作,因为修改N元树比二进制树更棘手.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!