文件系统及数据库系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页(页得大小通常为 4k), 这样每个节点只需要一次 I/O 就可以完全载入
将树的度 M 设置为 1024,在 600 亿个元素中最多只需要...有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点
当按照规则插入一个数到某个节点时,不能满足上面三个要求,就需要拆,先向上拆,如果上层满,则拆本层, 拆后仍然需要满足上面 3 个条件。...比如我们一串字符串需要检查拼写错误
数据: code cook Five File Fat
根据匹配这串字符生成的字典树
特点:
根节点不包括字符,除去根节点外 每个节点只包含一个字符
从根节点到叶子节点...,路径上经过的字符,对应的字符串
每个节点的子节点包含不同的字符(相同字符在下一层节点分裂)
此时演示特点三的情况
插入规则:
先查看节点是否存在,存在i向下遍历,不存咋创建新的节点
查找规则:
从根节点开始遍历...,如查找goodbye Good 找到前缀字符,但是此时字典树遍历完成,而单词并没有完成,结果任然不存在
删除规则
先要遍历出当前字符串路径,从叶子节点向上删除,除去叶子节点外的节点,如果有其他节点,此节点保留