# Balanced folder increment

I want to map an integer (let's say 32bits) to a valid path. The integer is an autoincrement value stored in the database.

I also don't want at any case any folder to have more than N subfolders. That is because in WIN-NTFS (for example) after a specific number (around 1000) things are going really slow.

So I devised a pattern where each integer is mapped to hex groupped in two digits. That creates 4 folders for each integer

For example:

``````1 -> '00/00/00/01'
2000 -> '00/00/07/D0'
70000 -> '00/01/11/70'
etc
``````

All nice and well.

But if you notice after creating the first 257 entries

``````the folder '00/00/00' will have 256 entries ('00' to 'FF')
folder '00/00/01' will have one entry
folder '00/00' will have 2 entries ('00' and '01')
and last folder '00' will have just one entry.
``````

The graph is higly unbalanced, the OS to finally find the folder '00/00/00/55' will have to search between 1+1+2+256 = 260 entries. If the graph was balanced it would be a search of 4 * Pow(257,1/4) =~ 16 entries

And my question is:

Is anyway I can transform the integer A to an integer A' that has the following properties:

• It's 1:1 transformation
• Can be inversed (for each A' I can can easily find A)
• For each 1..N, creating folders using the A' hex value, each folder has no more than Pow(N,1/4) entries

EDIT: I did test the two ciphers. The problem is that crypt functions output the whole 32bit range. I mean after 1000 increments and after each byte has a random value, the root folder has 256 different values (subfolders) and each of them have 1 or 2 entries. It's the same situation I started with. It's only inversed

• Can you please explain why you need to do this? – user82096 Dec 22 '15 at 11:10
• Off the top of my head, I believe git does something very similar to this (though with fewer layers) inside its internal refs folders. Though it might not be too helpful since it's mapping "abcdef" to a path like "ab/cdef". However, dan does have a point; why not directly store "00/00/07/D0" in the database, instead of storing 2000 and coming up with a mapping between the two? – Ixrec Dec 22 '15 at 11:44
• Encrypt the integer with a 32 bit block cipher and a fixed key. e.g. skip32 or ipcrypt. – CodesInChaos Dec 22 '15 at 12:32
• @CodesInChaos: They look good, thanks. They may not be the optimal solution, but they are good enough for my needs. I'll test them ASAP! – Panos Theof Dec 22 '15 at 13:03
• This is a pointless exercise. NTFS uses a B-tree, not linear search. Searching 260 entries doesn't take 260 comparisons, but approximately 10. Furthermore, the biggest actual problem is random disk I/O. 4 levels of directories means 4 disk seeks. – MSalters Jan 22 '16 at 7:36

Start with the modulo operation. That gives you X folders to start. As your ids grow, add an offset. An example, groups of 10 folders, 10 files per folder:

``````id < 100 : id % 10
Folders F0 through F9 -> Files are added in order, one in each,
then two, then... all the way to 10.

id >= 100 && id < 200: (id % 10) + 10
Folders F10 through F19 -> Files are added in order, et cetera

id >= 200 && id < 300: (id % 10) + 20
Folder F20 through F39

Etc...
``````

Of course, you'll want a different modulo (# of folders per group) and files per folder (1000?).

It's not entirely obvious, but the type of algorithm you're looking for is called a space filling curve. The space here is the namespace of folders.

XKCD had a 2D example a long time ago. It shows how the first 4 files would end up in `/00/00` to `/01/01` and the first 16 in in `/00/00` to `/03/03`. Expanding the algorithm, the first 256 files end in `/00/00` to `/0F/0F`.

In a 3D example, a space filling curve maps the first 8 entries from `/00/00/00/` to `/01/01/01` and the first 64 to `/00/00/00/` to `/03/03/03`. Expansion to N dimensions is straightforward from there, but as I mentioned in the comment suffers from excessive disks seeks.

This is not a direct answer but it does not fit in a comment. I just want to elaborate MSalters comment - internally, NTFS already does what you are trying to do.

It is a wrong impression about huge NTFS folder being slow. The wrong impression is usually due to the way some users interact with the folder - windows file explorer, which loads all entries when a folder is opened and it is supposedly to be slow. However, if you query one file with a specific name, it's instantaneous. Now you may ask, even if the program can always access the folder with specified file name, how about maintenance and support - say a support member needs to verify the existence of a file? In that case, go to command line and "cd" into the folder, use "dir filename". The result is still instantaneous. Of course, if you try "dir *21", then you will be served with the "table-scan" performance.

I once worked on a project involving a huge NTFS folder. It was all good until some manager decided to split the folder into smaller ones. Needless to say, it complicated the program unnecessarily and slowed down both the program and me when I need to do some support. In return, more developers and users felt comfortable with the folder when they needed to look up a file in that folder, which is actually one valid reason to split a NTFS folder.