storing two-dimensional arrays in jdbm

Help
2007-08-04
2013-06-03
  • Howard Katz
    Howard Katz
    2007-08-04

    I don't know if this is still an active forum or not -- I guess I'll find out soon!

    I'm new to jdbm and am trying to add persistence to an existing program in which a variety of data structures currently maintain program state entirely in memory. I'm trying to understand which jdbm-type structures are most suitable for persisting the various structures I'm currently using but am stumped on how to translate a few of them.

    I use a number of two-dimensional arrays for example. I can see how to emulate/persist a single-dimensional array by using its index as a key into either an htree or a btree, but I don't see how to do this in two dimensions. Can a btree entry contain another btree, for example? Or is there another way of doing this?

    TIA,
    Howard

     
    • Alex Boisvert
      Alex Boisvert
      2007-08-04

      Hi Howard,

      Actually, neither HTree nor BTree are good choices for arrays.   Typical operations on array are insertion and deletion at random points and neither {H,B}Tree will perform these in a scalable manner because they require changing the index of all elements in the array.

      Note they would be good choice if what you have are sparse arrays with few insert/deletes... mostly lookups.

      I would first reconsider the choice of datastructure (do you really need arrays?) or consider implementing a new data structure for arrays if that's what my need was, although arrays are notoriously expensive persistent data structures, hence why you don't find them in traditional database systems.

      cheers,
      alex

       
    • Howard Katz
      Howard Katz
      2007-08-04

      Thanks for your quick reply, Alex.

      Sorry, I'm still a bit confused. Just to make sure I'm communicating clearly, I was positing using the index of each array element as a key (assuming for the moment a single-dimensional array). So if I'm inserting element arr[ 10 ], I would do something like 

          BTree.insert( Integer.valueOf( 104 ), arr[ 104 ], ... )

      and then later if I'm then inserting arr[ 6 ], I would do

          BTree.insert( Integer.valueOf( 6 ), arr[ 6 ], ... )

      Does that seem like a reasonable approach?

      The arrays I'm maintaining aren't that large, so I could build/manipulate them entirely in memory first and then insert them sequentially in key/array index order once they're complete.

      Are you saying that inserting keys in sequentially increasing order is a good thing, a bad thing, or that it doesn't matter? I recall from early computer science 101 days that random inserts into a btree were better than monotonically increasing inserts -- but that was a long time ago!

      Howard

       
      • Alex Boisvert
        Alex Boisvert
        2007-08-05

        Hi again Howard,

        If you don't have duplicate keys, and do not require forward/backward navigation, the HTree will perform better for lookups and insertion.

        You're right about random insertions in a BTree being faster than ordered inserts, although the difference is not as large in a BTree as it is with a plain binary tree.   If you batch inserts in a single transaction, the difference will be even smaller since reordering BTree pages will happen in-memory as opposed to on-disk.

        cheers,
        alex

         
    • Howard Katz
      Howard Katz
      2007-08-04

      Whoops, that first example should have read: "So if I'm inserting element array[ 104 ], I would do something like ..."

      Howard