[ https://issues.apache.org/jira/browse/HDFS-7174?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Kihwal Lee updated HDFS-7174: ----------------------------- Description: When the number of children under a directory grows very large, insertion becomes very costly. E.g. creating 1M entries takes 10s of minutes. This is because the complexity of an insertion is O\(n\). As the size of a list grows, the overhead grows n^2. (integral of linear function). It also causes allocations and copies of big arrays. was: When the number of children under a directory grows very large, insertion becomes very costly. E.g. creating 1M entries takes 10s of minutes. This is because the complexity of an insertion is O(n). As the size of a list grows, the overhead grows n^2. (integral of linear function). It also causes allocations and copies of big arrays. > Support for more efficient large directories > -------------------------------------------- > > Key: HDFS-7174 > URL: https://issues.apache.org/jira/browse/HDFS-7174 > Project: Hadoop HDFS > Issue Type: Improvement > Reporter: Kihwal Lee > Assignee: Kihwal Lee > Priority: Critical > > When the number of children under a directory grows very large, insertion > becomes very costly. E.g. creating 1M entries takes 10s of minutes. This is > because the complexity of an insertion is O\(n\). As the size of a list > grows, the overhead grows n^2. (integral of linear function). It also causes > allocations and copies of big arrays. -- This message was sent by Atlassian JIRA (v6.3.4#6332)