Best SQL performance for block data

Discussion in 'Plugin Development' started by 0ct0berBkkitPlgins, Jul 2, 2019.

Thread Status:
Not open for further replies.
  1. Hello,

    I was wondering if there's any way to have O(1) complexity for query searches based on a block.

    To put that in simple terms, I'm trying to store data based on individual block coordinates. I'm wondering if there's any way I can make the SQL database equally fast for checking data at the block position, no matter if there's 100 blocks stored in the database or 100,000. My goal is for my plugin to not use up too much CPU when it comes to checking individual blocks.

    For some further clarification, I'm using SQLite for the database.
  2. Offline


    O(1)? No that is not possible. O(n) is the standard but if you use proper indexing you can achieve O(log n).

    O(1) is never achievable with database reads if you have more than one record. O(log n) is not bad though in most cases.

    Now that i think about it,
    For Minecraft block locations you're storing 3 coordinates. That makes a properly indexed query take O(log n) * 3. Y location is (pretty much) negligible, leaving you with a runtime of O(log n) * 2. Given you are using an index on X and Z coordinates.

    Do keep in mind having multiple indexes significantly impacts update times.

    However, without them, you are left with a runtime of O(n) * 2, which is a problem if you are storing hundreds of thousands of records, or if you read requently. You can get by with indexing only 1, either X or Y, coordinate if the dataset is small. If the dataset is really small you're better off not indexing at all. Simply put, the optimal approach is dependent on the size of the dataset. No one size fits all.
    Last edited: Jul 2, 2019
Thread Status:
Not open for further replies.

Share This Page