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 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
