数据结构-常用树实现

• 目前情况

  种类名称	简介	使用场景	是否实现
  二叉搜索树	利用左右子树的规则，来减少查找时递归深度	数据查找	✅
  AVL树	高度平衡二叉查找树，左右子树高度差不超过1	查找多，数据变动少	✅
  红黑树	根黑叶黑，红带两黑。非叶到叶黑树相等，且路径相差不会超过1倍，非高度平衡	数据变动多。Java TreeSet ConcurrentHashMap	✅
  B树	多路查找树，分支多、树矮，磁盘IO少。n个子树节点包含n+1个关键字	B树相较B+树可把HotData放在Non-leaf以快速查找
  B+树	多路查找树，分支多、树矮，磁盘IO少。n个子树节点包含n个索引关键字，数据存叶节点	快速遍历数据(二分查找)。文件系统、索引
  Trie树	字典树，不同字符串的相同前缀共享保存一份	前缀匹配，统计和排序大量的字符串
  LSM树	延迟、批量更新（滚动合并）；写内存效率高；读效率略低	LSM树适用于长期具有高频次数据更新而查询较少的场景