二叉查找树(Binary Search Tree)

根节点的值大于其左子树中任意一个节点的值,小于其右节点中任意一节点的值,这一规则适用于二叉查找树中的每一个节点。

用二叉查找树实现词典

使用二叉查找树实现词典时,要先将数据对(的列表)按照单词的词典顺序排列,然后存储到存储器中。

数据对是由单词和对应着该单词的倒排列表的引用信息构成的。

优点:

  • 如果词典能够完整地加载到内存,那么所形成的二叉树的搜索效率将会非常高。

缺点:

  • 如果词典存储到二级存储器上时,效率非常低。

备注:

  • HDD或SSD等二级存储器一般被称作“块设备”,由于它们是以块为单位进行输入输出的,所以即使只是读取块中1个字节的数据,也不得不对整个块进行输入输出操作。
  • HDD的最小输入输出单位是512字节的扇区。文件系统通常以页为单位来管理存储空间(空间大小是设备块大小的常数倍),并以页为单位进行输入输出。Linux通常以4KB为一页。(4K对齐)

用B+树实现词典

在B+树中,所有的记录都存储在树中的叶结点(Leaf Node)上,内部结点(Internal Node)上只以关键字的顺序存储关键字。

B+树通常以文件系统中页尺寸的常数倍为单位管理各结点。

文档更新时间: 2020-03-11 09:53   作者:admin