算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)

  • 时间:
  • 浏览:0

1.局部性原理与磁盘预读

可能性磁盘的存取速率与内存之间鸿沟,为了提高速率,要尽量减少磁盘I/O.磁盘往往都是严格按需读取,只是每次都会预读,磁盘读取完前要的数据,会顺序向后读一定长度的数据倒进内存。而曾经 做的理论法律办法是计算机科学中著名的局部性原理:

接着来搞树!

可能性磁盘顺序读取的速率很高(不前要寻道时间,只需很少的旋转时间),只是对于具有局部性的系统程序来说,预读能够提高I/O速率.预读的长度一般为页(page)的整倍数。

在系统程序员小灰的公众号里提到了1个多多概念——卫星数据:索引元素指向的数据记录,比如数据库中的某一行。在B+树中能够能 叶子节点带卫星数据,有些的里边节点只是索引,没人任何数据关联。在数据库的聚集索引(Clustered Index)中,叶子节点直接暗含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点暗含指向卫星数据的指针。 吧

堆是1个多多完整版二叉树,大顶堆只是每个节点都是大于它的父节点。

插入和删除时间简化度都是O(logn)。

红黑树的插入、删除、查找最坏时间简化度都是O(logn)。

红黑树理解概念就OK了,目前不深入研究。

推荐一篇很好的对红黑树的概念理解文章:

漫画:什么是红黑树?

支持云栖社区,也希望有些人能支持下我的独立博客——白水东城

文章地址:

算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充

文章地址:

算法之树(二,B+树、哈夫曼树、堆、红黑树)(Java版)-持续更新补充参考

当1个多多数据被用到时,其附过的数据也通常会马上被使用,系统程序期间所前要的数据通常比较集中

初始化1个多多堆,只是把无序数组的每个值都依次插入堆中,只是总爱删除,把被删除的元素倒进数组的最后1个多多有效元素并且 的位置。

二分查找,二叉树查找都依赖特定的数据型态,分别是待查找数据有序、二叉查找树,显然数据四种 能够 完整版满足各种数据型态。

很多很多 ,数据库除了维护数据之外,还维护者满足特定查找算法的数据型态——索引,索引以四种 法律办法引用数据,曾经 就能够在索引的基础上实现高级的查找等操作。目前大累积数据库系统和文件系统都采用B树可能性变种的B+树来作为索引型态

并且 数据型态课上用C写过哈夫曼树,Java的暂时不搞了,并且 遇见再回来补充。

2.数据库索引采用B+树的主要导致 分析

根据里边的局部性原理和磁盘预读,B树中用了四种 技巧:每次新建节点时,直接申请1个多多页的空间,曾经 就保证1个多多节点物理上也存储在1个多多页里,加之计算机存储分配都是按页对齐的,就实现了1个多多结点只需一次I/O。

B树在提高了IO性能的同時 并没人防止元素遍历的速率低下的疑问,正是为了防止四种 疑问,B+树应用而生。B+树只前要去遍历叶子节点就能够实现整棵树的遍历。只是在数据库中基于范围的查询是非常频繁(比如查询某段时间之内的数据)的,而B树不支持曾经 的操作可能性说速率太低(前文可能性说明速率低的导致 分析)。

带权路径长度最小的树就叫最优二叉树,也只是哈夫曼树。要使带权路径长度最小,没人权值大的点就应该离根节点越近。

构造法律办法:先从小到大排序,只是取舍最小的两棵树合并,重复这1个多多步骤。

可能性对一段英文转换为二进制传输,采用哈夫曼编码,让频率高的用短码,频率低的用长码,只是保证不要有某个字符的串是曾经 字符的前缀(可能性可能性每个字符的长度不一样会再次出先曾经 的疑问,比如,1个多多字符被11表示,曾经 被110表示,再次出先一段11011,曾经 都是歧义)