Trie树，即字典树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。 Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    在游戏AI中, 常见的实现有决策树、状态机等, 它们各自存在着不足. 以状态机FSM为例, 它非常难以通用和扩展, 状态转化的复杂度随着每个新增状态将变得越发缭乱. 考虑到可能存在多个并行的状态机, 它们之间的交互更是复杂交错, 难解难分. 于是大神们创造了行为树(BehaviourTree),

    ​1972 年 R. Bayer 和 E. McCreight 的论文（参考资料 [1]）提出了 B- 树。B- 树是一棵平衡树，与一般的平衡二叉树（AVL，红黑树等）不同的是，B- 树的每个节点最多可以拥有 m（m>=2）个元素，（m+1）个子节点，并且所有的叶子节点位于同一层。B- 树的查找和插入的时间复杂度和二叉树一样，都是 O(logn)，但因为每个节点保存的元素比较多（一般是几十个到几百个之间），树的高度比一般的二叉树要小很多，访问硬盘次数更少，在数据不能全部加载到内存的时候比一般的二叉树效率要好。

    二叉树： 一个根节点，每个节点下挂着最多2个子节点。、 概念： 度：结点的分支数，二叉树度为2。 深度：树的层次。 二叉排序树： 二叉树的基础上，每个节点上都有一个数字，节点上的数字都比右节点上的大。 应用场景： 基于内存的排序数据结构，写入时将数据写入到对应的位置。数据可能会出现倾斜，可以想到数字写入顺序如果不是50-20-60-18-55，而是18-20-50-55-60，那么二叉树就会退变为链表。 B-树： B-树每个节点上包含着数据和指针，每个指针指向其一个子节点的位置，并且数据的个数为指针的2d-1个。这里的d是指针的个数，同时也是树的“度”。 B-树的查找需要一次对每个节点进行二分查找，直至找到或返回null。通常，可以引入布朗过滤器等方式加速查找。 B-树的写入、删除时要进行分裂、合并、转移等操作，越是非顺序的插入就越容易碰到这些高性能消耗的操作。