Feature #644
Von Maximilian Seesslen vor 10 Tagen aktualisiert
Iterating over all entries takes much time. Binary search would be quite fast.
<pre>
S=7
[1] [2] [3] [4] [5] [6] [7] [8] [9]
L R
C=(L+R)/2
if(*C < S )
L=C;
else if (*C > S )
R=C;
else
found;
C=5; L=5; R=9;
C=7; found;
</pre>
On 32GB 35 sectors have to be read;
(2^26) × 512 2^35 = 34359738368
(16 (35 × 512) / 1024 = 13KB 17,5 have to be read to find starting block.
This can be done in another state.
<pre>
S=7
[1] [2] [3] [4] [5] [6] [7] [8] [9]
L R
C=(L+R)/2
if(*C < S )
L=C;
else if (*C > S )
R=C;
else
found;
C=5; L=5; R=9;
C=7; found;
</pre>
On 32GB 35 sectors have to be read;
(2^26) × 512 2^35 = 34359738368
(16 (35 × 512) / 1024 = 13KB 17,5 have to be read to find starting block.
This can be done in another state.