介绍一下B+树和LSM树。

文件索引和数据库索引

  1. 大部分用B+树,少部分用B树。
  2. 哈希表虽然能够在 O(1) 查找到目标数据,但要进行模糊查找的话,却只能遍历所有数据。另外如果出现了极端情况,哈希表冲突的元素太多,也会导致线性时间的查找效率的。
  3. 二叉查找树虽然也很快,但由于文件索引是存放在磁盘上的,所以不仅要考虑查找效率,还要考虑磁盘的寻址加载次数。

B树

  1. B树相当于是一棵多叉查找树。
  2. 实际上磁盘的加载次数,基本上是和树的高度相关联的。高度越高,加载次数越多,高度越矮,加载次数越少。所以对于文件索引的存储,一般会选择矮胖的树形结构。