阐述什么是ElasticSearch 字典树?
ElasticSearch中的字典树(Trie)是一种用于存储和检索字符串的高效数据结构。每个节点表示一个字符,路径表示一个字符串。字典树的主要优点是能够在字符串集合中快速查找具有相同前缀的字符串。
字典树有3个基本性质:
- 根节点不包含字符。
- 除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
此外,对于中文的字典树,每个节点的子节点用一个哈希表存储,这样不用浪费太大的空间,而且查询速度上可以保留哈希的复杂度O(1)。