本文共 319 字，大约阅读时间需要 1 分钟。

1、红黑树

红黑树是一种平衡二叉查找树，它是为了解决普通二叉查找树在数据更新过程中，复杂度退化的问题而产生的。红黑树的高度近似log2n，所以它是近似平衡，插入、删除、查找的时间复杂度都是O(logn)。

2、B+树

正是因为要时刻保证 B+ 树索引是一个 m 叉树，所以，索引的存在会导致数据库写入的速度 降低。实际上，不光写入数据会变慢，删除数据也会变慢。这是为什么呢？ 我们在删除某个数据的时候，也要对应的更新索引节点。这个处理思路有点类似跳表中删除数 据的处理思路。频繁的数据删除，就会导致某些结点中，子节点的个数变得非常少，长此以 往，如果每个节点的子节点都比较少，势必会影响索引的效率。

B+ 树的结构和操作，跟跳表非常类似。

转载地址：http://klbii.baihongyu.com/