[dm-devel] btree vs. linear seach in device mapper

[Mikulas Patocka]

On Thu, 4 Apr 2013, Mikulas Patocka wrote:

> There are no scalability problems regarding performance - device mapper 
> uses btree to search the target table, so the number of target don't 
> affect performance.
> 
> device mapper uses vmalloc to alloc all targets linearly, so it is limited 
> by avaiable vmalloc space. It is not a problem on x86-64, but it is 
> limited on x86 - vmalloc space can be as low as 128k (one target structure 
> has 64 bytes for 32-bit architectures and 96 bytes for 64-bit 
> architectures).

BTW. when I see that btree code in dm-table.c, I ask - why doesn't it use 
binary search?

We only append targets at the end when constructing the device, we never 
insert or remove them, so we don't need a tree. For these operations 
binary search would be as good as btree and it is simpler.

Mikulas