Re: Modestly announcing my first library cl-bplustree (in memory B+ tree)

[Bernd Nawothnig]

On 2012-08-21, ebobby wrote:
> cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.

What sense makes an in-memory implementation of a data structure that
is specifically designed to work best on disks (block based devices)?




Bernd
--
"Die Antisemiten vergeben es den Juden nicht, dass die Juden Geist
haben - und Geld." [Friedrich Nietzsche]

[Pascal J. Bourguignon]

Bernd Nawothnig <Bernd.N...@t-online.de> writes:

> On 2012-08-21, ebobby wrote:
>> cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.
>
> What sense makes an in-memory implementation of a data structure that
> is specifically designed to work best on disks (block based devices)?

It was designed for disks, when disk accesses were 10,000 slower than
memory accesses.

Nowadays, RAM accesses are 1,000 slower than L1 cache accesses…

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Bernd Nawothnig]

On 2012-08-23, Pascal J. Bourguignon wrote:
> Bernd Nawothnig <Bernd.N...@t-online.de> writes:
>
>> On 2012-08-21, ebobby wrote:
>>> cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.
>>
>> What sense makes an in-memory implementation of a data structure that
>> is specifically designed to work best on disks (block based devices)?
>
> It was designed for disks, when disk accesses were 10,000 slower than
> memory accesses.
>
> Nowadays, RAM accesses are 1,000 slower than L1 cache accesses…

When you read a block from the disk which is the the smallest directly
accessible item there you will automatically read a whole B(+) node
(if all is properly designed and set up). That is not the case when
reading data from RAM. There you can access even a single Byte without
comparable penalties for reading much more than you need to to read.
The L1 cache does not read fixed blocks like a disc controller. So an
in-memory B(+) tree is unnecessary complicated.

[Pascal J. Bourguignon]

Bernd Nawothnig <Bernd.N...@t-online.de> writes:

> On 2012-08-23, Pascal J. Bourguignon wrote:
>> Bernd Nawothnig <Bernd.N...@t-online.de> writes:
>>
>>> On 2012-08-21, ebobby wrote:
>>>> cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.
>>>
>>> What sense makes an in-memory implementation of a data structure that
>>> is specifically designed to work best on disks (block based devices)?
>>
>> It was designed for disks, when disk accesses were 10,000 slower than
>> memory accesses.
>>
>> Nowadays, RAM accesses are 1,000 slower than L1 cache accesses…
>
> When you read a block from the disk which is the the smallest directly
> accessible item there you will automatically read a whole B(+) node
> (if all is properly designed and set up).
> That is not the case when reading data from RAM.

Yes it is. When you access a single byte in the RAM, you load whole
cache lines, that is blocks of 64 or 128 bytes. This corresponds to the
sector size of a hard disk.

> There you can access
> even a single Byte without comparable penalties for reading much more
> than you need to to read. The L1 cache does not read fixed blocks
> like a disc controller.

Of course it does. How else do you think it works?

> So an in-memory B(+) tree is unnecessary complicated.

My argument is that it might be useful to deal with the speed
differential between cache and RAM, if well adjusted so that it limits
out-of-cache-line memory accesses.