这些树主要用于提升磁盘IO的效率，磁盘IO一般以磁盘页为单位，树上每个节点对应一个磁盘页，使用二叉查找树会增加IO次数，效率低。
B树
对于M叉树，每个节点关键字个数是 M/2上取整-1到M-1，孩子数比节点关键字个数大1。
根节点至少有两个孩子
B+树
节点关键字个数等于孩子数，数据全存在叶子节点，其他节点只存在索引，没有数据指针，所以每个节点可以存更多的关键字，只要不超过磁盘页的大小，所以IO效率更高，数据全在叶子节点，并通过指针行成有序链表，因此对范围查找很友好。
B*树
每个节点的关键字个数至少为2/3M个，空间利用率提高
中间节点增加了指向兄弟节点的指针，在当前节点数据满了之后。可以将一部分数据放到兄弟节点中，再在原节点插入，若兄弟节点也满了，就在当前节点和兄弟节点之间新建一个节点，并复制这个两个节点1/3到新节点中。
而在B+树中当前节点满了 就直接新建节点，所以B*树的新建节点的概率降低了。
Tire树
又称为字典树（适用于查询前缀匹配字符串），搜索引擎的提示功能可以用tire树来完成，根节点不存放值，将单词拆分成一个个字符放在节点中，每一个节点的所有孩子可以用一个数组来表示，数组存放a-z，在相应字母下存放指针。
时间复杂度O（n），空间复杂度高，所以可以用缩点优化来将最后的几个节点放在一个节点中。
skiplist 跳表，redis中的有序链表使用跳表来实现，还有散列表
跳表相当于给链表加上了索引，时间复杂度为O（logn），空间复杂度是O（n）。
网友评论