A journey to searching Have I Been Pwned database in 49μs
This and other similar solutions seem <i>awfully</i> over-engineered.<p>a) Hashes are constant size (20 bytes for SHA1)<p>b) You only care if they&#x27;re present or not in the database. There&#x27;s no associated variable length data.<p>The simplest yet <i>very efficient</i> format is simply a sorted array of &quot;byte[20]&quot;, with binary-search as the lookup. No headers, no pointers, no custom format of any type. Literally just 20 x n bytes where &#x27;n&#x27; is the number of hashes. Lookup of the &#x27;n-th&#x27; hash is <i>just</i> multiplying &#x27;n&#x27; by 20.<p>If you really, <i>really</i> want a B-Tree (why?), just stuff it in <i>any</i> database engine. Literally anything will handle a single fixed-length key lookup efficiently for you.<p><pre><code>    CREATE TABLE &quot;HIBP&quot; ( &quot;SHA1&quot; BINARY(20) PRIMARY KEY );
    SELECT 1 FROM &quot;HIBP&quot;
    WHERE &quot;SHA1&quot; = 0x70CCD9007338D6D81DD3B6271621B9CF9A97EA00
</code></pre>
There. I solved the blogger&#x27;s problem in literally under 5 minutes without having to write a custom binary.<p>You can trivially query databases from both web apps and CLI tools, and you can do this with batch queries too. E.g.: WHERE &quot;SHA1&quot; IN (... list... )<p>PS: Text-based tools (such as most shell tools) suck at this type of binary data. The newline terminated hex representation is 41 bytes per hash, so just over double the required size. Clever 5-10% prefix compression tricks pale in comparison to <i>not doubling</i> the data size to begin with.<p>PPS: A pet peeve of mine is older Java database &quot;enterprise&quot; applications that use UCS-2 &quot;nvarchar&quot; text columns in databases to store GUID primary keys. The 16 byte GUID ends up taking a whopping 78 bytes to store!