数据结构

参考文档

• 数据结构在线可视化工具 (opens new window)

树

二叉树

特点：

• 每个节点只能有 2 个子节点。
• 左边小于右边。

缺点：

• 当数值连续插入时，树的结构退化成了链表，不再可以提高搜索效率。

  

• 由于每个节点只有 2 个子节点，数据越大，树的深度较大。

红黑树

特点：

• 每个节点只能是黑色或红色。
• 根节点必须是黑色。
• 红色的节点，它的叶子节点只能是黑色。
• 从任一节点到其叶子节点的所有路径中都包含数目相同的黑色节点。

缺点：

• 数据依次插入时候，仍然会偏置一边，导致树的高度非常高。

  

• 树的深度问题。

B-Tree

B 树，也叫做 B Tree 或 B-Tree，是一个多路平衡搜索树。

• degree（阶） 指的是子节点个数，也是指针数，并非 key（data） 的个数。
• 树的某个节点的指针数等于 degree 之后，会生成分支结构，中间元素会上升，1 2 <- 3 -> 4 5。

特点：

• 一个节点可以有多个元素。
• 叶子结点具有相同深度，叶子结点的指针为空。
• 所有索引元素不重复。
• 节点中的数据索引从左到右递增排列。

缺点：

• 范围查询依然效率很低。
• 查询效率不稳定。
  • 例如图中，查询 20 只需要 1 次，而查询 3 则需要 3 次。
• 树的高度仍有下降空间。

B+Tree

B+ 树解决了 B 树的问题。

特点：

• 非叶子节点不存储数据，只存放索引，可以放多个索引。
• 数据全部存放在叶子节点，并包含所有的索引字段。
  • 数据裂变后，中值上升，但是会留存一份同样的值在叶子结点。
• 叶子节点用指针连接（单向链表），提高区间查询性能。

讨论区

由于评论过多会影响页面最下方的导航，故将评论区做默认折叠处理。

点击查看评论区内容，渴望您的宝贵建议~