Re: [PATCH 2/2 v2] Btrfs: check if directory has already been created smarter

[Liu Bo <bo.li.liu@oracle.com>]

On Thu, Feb 27, 2014 at 04:01:23PM +0800, Wang Shilong wrote:
> On 02/27/2014 03:47 PM, Liu Bo wrote:
> >Currently to check whether a directory has been created, we search
> >DIR_INDEX items one by one to check if children has been processed.
> >
> >Try to picture such a scenario:
> >    .
> >    |-- dir            (ino X)
> >          |-- foo_1    (ino X+1)
> >          |-- ...
> >          |-- foo_k    (ino X+k)
> >
> >With the current way, we have to check all the k DIR_INDEX items
> >to find it is a fresh new one.
> >
> >So this introduced a rbtree to store those directories which are
> >created out of order, and in the above case, we just need an O(logn)
> >search instead of O(1) search.
> Just a reminder, we ususally call O(n) rather O(1) here.
> If we falls O(1) to O(logn)..things are becoming worse~~

Good catch, my bad.

thanks,
-liubo