开发者

What are the disadvantages of red black trees?

From all what I been reading about Red - Black trees it seems like they are the best data structure for storing data.

I am trying to build a database and I am wondering, just in the aspect of Red - Black trees implementation, where should I be mor开发者_如何学Ce careful and what I should not do.

Are the Red - Black is really that perfect?


It depends on how you need to query and update the data. If, for instance, you do not need ordered data, hashmaps are likely better, since they have (expected) constant time lookup/insert instead of logarithmic. Even if you do need ordered data, red/black trees might not be perfect - in particular, not if you are implementing a disk-based database. In disk-based I/O, seeking is expensive compared to sequential block reading, and the goal is therefore to minimize the number of disk accesses. In such cases, B-trees (or B+-trees, or B*-trees) are better - these are all designed for being fast when stored on disks.


Red-Black trees are far from perfect for ALL data access. They have their place but other methods such as hashed maps and plain old lists are better in a lot of cases.

One notable disadvantage of a red black trees in a lot of cases is that it is a binary tree and thus lookups are O(lg(n)) where as hash tables have a lookup of O(1).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜