大型 Trie 树数据库的尝试，期望在 RAG 系统中发挥作用

[bigtang]

搜索了天工 AI, perplexity, GPT4, 全世界尚无一个独立的商业 Trie 树数据库产品。

http://xt.tanglib.com/ 是一个 Trie 树数据库，上线半年，还是很稳定的。

大型 Trie 树数据库是有难度的（ xt.tanglib.com 的文本数据接近 1T ，单机应该算大型了），否则早就诞生了。

Trie 树数据库相对于 ElasticSearch 倒排索引数据库有一些独特优势，例如速度更快，可以支持插入删除。

最近流行 RAG 系统，特发帖在 v2ex, 期待愿意用 Trie 树数据库的项目来谈合作。

欢迎大家体验这个 Trie 树数据库。

科普一下，Trie 数据库特点：

对于 "abcdefgh", Trie 树数据库可以搜索 “abc", "abcde", "bcdef", "cdefgh", "defg" 等任意连续序列，适合提供素材。

在 RAG 系统中，AI 与 Trie 树数据库结合应该是很完美的，Trie 树数据快速提供素材，AI 综合判断逻辑。

RAG （ Retrieval-Augmented Generation ）检索增强生成，即大模型 LLM 在回答问题或生成文本时，先检索出相关信息，然后生成文本，提高回答的质量。
向量检索的弊端：向量检索是基于词向量的相似度计算，如果我们查询“8XLARGE64”，“99.9%”，这样的一些关键字时，向量搜索会得出一些毫不相干的内容，这种 trie 数据库的优势就出来了。

适当的做法是：用户提一简单问题，LLM 根据上下文及背景及同义词，向 trie 数据库发出 100 条查询，trie 的响应是毫秒级，然后根据这些中间结果生成回答。

[miniliuke]

你不会是索引结构是字典树就叫 Trie 树数据库吧......

[buaasoftdavid]

没有诞生的原因有没有一种可能是因为这是个伪需求？

[bigtang]

楼上你心目中的 Trie 树数据库是什么样的？

知乎上有个问题：Trie 树非常适合索引结构，怎就没人用于数据库引擎？
https://www.zhihu.com/question/643972502/answer/3393671711

[cowcomic]

之前做过基于 Trie 树的内存级词匹配
感觉 trie 树的构建对于内存的消耗还是挺大的
而且搜索感觉是 Trie 树的逆向使用呢，好奇怎么做的

[bigtang]

@cowcomic 看来研究过 trie:) @buaasoftdavid 有可能是，如果 chatgpt3 不出来，整个 AI 都是“伪需求”

[fakepoet]

小小的鸡毛一下，可以叫 `Trie` 或者叫 `字典树`，但是 `Trie 树` 有点语义问题。

[maggch97]

额额，只能搜索精确子序列，不知道怎么硬和 ai 扯上关系的
存储也是 26 倍普通结构…

[maggch97]

@maggch97 子串，26 还是只有小写字母的情况

[yeekal]

trie 内存占用太大，ElasticSearch 倒排索引跟 trie 不矛盾，如果你把分词粒度调到 1 ，理论上 trie 能检索到的，ElasticSearch 也可以

[shyrock]

理论上对于离散的数据，也就是搜索词不是紧靠在一起的情况，trie 搜索不到吧。

在 OP 的网页上试了一下，感觉不符合一般的搜索习惯。
比如说正常搜索阿里公司 名叫马云的人，输入阿里 马云就搜不到，实际上这条记录是存在的。

[bigtang]

@shyrock 这个网站的数据里真不存在 “阿里 马云” 阿，你看着数据再挑两个词看看

[bigtang]

@yeekal trie 数据库就是比 ElasticSearch 粒度设为 1 要优秀得多，否则就毫无意义了

[pkoukk]

AI 用的是向量数据库....
OpenAI 提供的知识库自训练 embeddings 数据可以直接存进向量数据库里去
https://platform.openai.com/docs/guides/embeddings/frequently-asked-questions
Trie 在 AI 里不能说毫无用处，起码也是没有屌用，ana 和 anal 两个词可是天差地别

[bigtang]

@maggch97 @pkoukk 跟 ai 的关系是：例如用户问 Q10G 电视是否效果好？ trie 很快能搜到很多 Q10G 电视及评价，送给大模型判断。实际的型号可能是 tcl 75q10g, tcl85q10g, 当然你说 elasticsearch 也能搜到，我告诉你同等条件下 trie 更优秀。

跟向量数据库的区别是性能及易用性上的区别，向量数据库的匹配跟 ai 还是差很远，且向量数据库只能是含义上的匹配，就刚才这个 Q10G 电视是否效果好 我怀疑向量数据库能否准确排除非 Q10G 。

[matrix1010]

10 楼的意思是，比如我想搜 ab OR de OR gh, Trie 是否能做到，是否比倒排索引性能更高？

[shyrock]

@bigtang 你自己随便找你工商数据任意一行，把公司和人名两个关键字拿去搜一下就会发现问题了。

[bigtang]

@matrix1010 @shyrock 求交集问题是无解的，a 有 10 亿个，b 有 10 亿个，求 a and b, 只能遍历，不要问不可能的问题。
但 ai 解决这种实际问题不难，a 有 10 亿个，加一些背景限制，缩减到 3 万个，遍历就快了。

[shyrock]

@bigtang 你要把思路限定在只用 trie 来搜索，当然很难。。。

你看下 baidu 或者 ES 搜索就知道了，这个是非常高频的需求，而且换个方法就并不是那么难解决。

[maggch97]

我只觉得你的数据结构知识学的很一般。首先 trie 做存储并不是什么特立独行的想法，每个刚学数据结构的人都会觉得这个结构简直无敌，非常适合做数据库。
但是为什么这么简单的结构，看起来这么 work 的想法还没有成熟的项目应用呢。聪明的人知道去搜一下前人的讨论，“固执”的人会真的搞出来并强行推销给大家，不过并没有人接受就是了。

[maggch97]

我觉得你既不懂数据结构，也不懂数据库，更不懂 AI

[bigtang]

@shyrock 你说的是 TF-IDF 还有 pagerank 这些？ tanglib 目前只做了半个解决方案，ai 与 tanglib 之间可进行多次交互，发现关键词量太大继续限定，而百度以及原来的搜索必须一次给出结果，其实这些方法都很大概率不可靠，很多时候明明知道有百度就是找不到，这种时候不少吧？

[nomagick]

字符精确匹配才是真正的小众需求。。。

[bigtang]

@nomagick 我说的是给 ai 提供素材，不是给最终用户。。。

[iosyyy]

@bigtang #21 百度多少数据你这才多少数据百度乃个肯定要按中文做分页你这个 有百度 1/1000 的数据就爆了好吧

[bigtang]

@iosyyy 你说的爆了是怎么爆？是查询时间爆了？我只有 1 台服务器阿，百度有 10 万台。。。
欢迎质疑

[caixiangyu17]

其实好不好用，拿数据说话就好了。来相同的大数据，做一个压力测试瞧瞧，数据直接放上来，地下就不是质疑的声音，而是膜拜大佬了。现在每个性能完不完爆都是嘴说的，有什么意义了？

[victorc]

空间浪费太严重了，我 10 多年前做搜索 输入框 suggestion 的时候，最开始用 trie ，非常消耗空间，后面改成常规 倒排索引实现（有序数组+二分法查找），速度/空间 都满足