<p>Programmers often forget that we tends to read more code than we write. But what they forget more often, is how changes affect the mental effort required to understand the code. I refer to this as mental complexity. This mental complexity tend to increase with every addition, it increases tenfold when adding features or adding constraints on some shared context within your application. Even if problems with consistency and concurrence are ignored, shared state is still seen as a bad practice. And I share this view, but not because it is a common source of bugs. Using shared state does not introduce a bug, the bugs are a symptom of something else. The underlying issue all comes down to the strain it puts on your mental model.</p>
<p>While programming you often build up a mental model of everything you need to know and use. For smaller programs everything fits perfectly in your brain and using shared state will not cause much problems (yet). But with every addition this mental model increases, causing all kinds of problems. Developers will start to forget that some things existed, forget to change some shared variable or forget that "no at this stage in the program, you cannot use that variable or it has been changed by something else". The size and the burden of this mental model is determined by multiple factors, on multiple different levels. Let's start by examining how we build this mental model when we try to understand an arbitrary piece of code.</p>
<p>When you try to understand a certain piece of code, you'd often look at specific units like a class, a method or a function. Each of these have their own 'context'. This context is a combination of scope, the state of everything in scope and how this state changes over time. With scope we mean every variable, class and function a certain unit of code uses. The scoping rules mostly depend on the rules of your programming language, but these are consistent throughout your code. In contrast, your state changes all the time. The current function can change local variables, variables outside its local scope or through a reference passed as an argument. All of this would influence the scope of the piece of the your are looking at. Thus also affecting the effort required mental to build this mental model.</p>
<p>Needless to say, the more things are in scope, the bigger the strain on the mental model is. On top of that, the more different calling states it has, the bigger the strain on the mental model. And lastly, the more the state changes throughout the function, the bigger the strain on the mental model. Lets look at a favoured programming concept as an example: Pure functions. Pure functions are functions which are side effect free and their output are a one to one mapping with there input. No state, no side-effects, fully predictable. There scope is reduced to a minimum, it is as big as there input arguments. What is more, they are side-effect free, meaning that they will not cause a state change anywhere else, which further limits the changes we need to track and thus the strain on our mental model. In contrast, global variables have a huge strain on your mental model, because potentially any piece of code in your program can use it and thus it increases the mental strain on every line of code.</p>
<p>But this affects every line of code you change, and with every library you add, most things you add, add to the mental strain. This mental model also ties in really neat with other common good practices! To start with dependency injection instead of a shared container, which reduces the scope of a piece of the. Using smaller interfaces instead of concrete implementation, which limits the scope of all clients of said interface. Keeping your functions smaller, which reduces the size of the context you need to keep in mind. Immutable objects instead of long lived mutable object, which eliminates the change you need to track throughout the objects live time. Thus all these good practices try to reduce the mental strain, which increases the maintainability of your code.</p>
<p>So instead of increasing complexity by carelessly creating new concepts throughout your code. Try to think about what your additions do in terms of mental strain. Try and write code with the smallest scope and context, while reducing side-effects and variable changes. Not because somebody says so, it is called a good practice or it is the cool thing to do. But because this reduces the processing power required to read the code and it will be easier for anybody, new and veteran alike, to join in. Keep an eye out for the mental strain your code produces.</p>


Most programmers know not to keep global or shared state, and when you do, do it so less as possible. But why shouldn't we ? Why is it so bad to use shared state and how does it relate to other constructs such as dependency injection and pure functions.

The mental complexity of code

<p>Developers tend to read more code than they write. Thus every improvement to make our code more readable is a huge bonus for our future selves and our fellow developers. Even more so with open source, where readability is a must, nobody is going to contribute if your code is a complete mess and unreadable. I am not going to say we need to comment more or anything, comments are not the best tool to make your code more readable. You can read more about why I think that in <a href="/blog/2021-02-13-why-comments-dont-make-your-code-more-readable">another blog post</a>.</p>
<p>An important thing is that your programs can tell a story. As Robin C. Martin put's it in his book 'clean code': Master programmers think of systems as stories to be told, not programs to be written. But this doesn't tell us how we do it, so let's start!</p>
<h2>Don't write for yourself</h2>
<p>The first thing to realize is the fact that you should not write code for yourself. The fact that you understand what you did is simply not good enough. Always ask yourself if other contributors will understand the code? And most importantly if far-less experienced coders will understand your code. If so, your future self will most certainly understand the code.
I cannot iterate this enough though. If you assume the readers of your code are really, really stupid. You will be able to understand the code with ease when you take a fresh look at it in the future. So lay off on all your fancy language tricks and one-liners, inexperienced coders don't get that. Don't put personal jokes or references in the codebase, nobody besides you will understand it. So keep it simple.</p>
<h2>Know your tools</h2>
<p>Knowing which tools you have to make your code more readable is half the battle. If you assume you can only add comments, you probabily will end with a lot of readable content, but not with readable code.
My readable code toolbox consists of the following:</p>
<ul>
<li>Naming</li>
<li>Putting code in named functions</li>
<li>Restructuring the code</li>
<li>Refactoring the code</li>
<li>and dead last: explanatory comments</li>
</ul>
<h3>Naming</h3>
<p>First up and most importantly: naming. You probably heard this a lot already, but good names will do a lot for readability. In most languages you can name various things like: Variables, Functions and classes (or/and types). But what are considered good names?</p>
<p>Well, we want to pack as much clear and readable information in all names if possible. So things like <code>i</code> , <code>iX</code>, <code>a</code> or other very small variable names are not good enough. With one exception however. It is very common to use <code>i</code> as a counter in a for loop. This has become so iconic, that this packs so much information in it, that it is fine. Abbreviations should be avoided most of the time since it is hard to read and understand it in code. There are exceptions however common or domain specific abbreviations can be used, everybody should know common abbreviations like HTTP and FTP and typing them out is just silly. But made up abbreviations, for model names or from outside of your domain should never be used, they tend to introduce confusion and these are hard to read for new developers.</p>
<h3>Function</h3>
<p>Next on the list is putting code in named functions. So we developers got this thing, where we can put lines of code that do a certain thing in a function with a handy name we can specify ourself. Use it! I myself actually used to believe that functions were only useful for code reuse. But ohhh boy, you can make some horrible blurry code really readable by putting every few lines in a function.</p>
<p>Take for example the snipped below.</p>
<pre><code class="language-php">public function calculateAndAssignLoyaltyPoints(Order $order): void {
    $this->promotionApplicator->apply($order);

    if ($order->paymentState === 'completed') {
        $this->loyaltyAssigner->assign($order);
    }
}
</code></pre>
<p>In the above code sample the <code>loyaltyAssigner</code>, <code>order</code> and <code>promotionApplicator</code> are part library (so for simplicity lets consider them immutable). The code is pretty small already so what can we do to make this understandable. I know what this does, but without checking the promotionApplicator and loyaltyAssigner you will have a pretty hard time understanding. Let me clarify it a bit.</p>
<pre><code class="language-php">public function calculateAndAssignLoyaltyPoints(Order $order): void {
    $this->calculateAndApplyOrderPromotions($order);

    if ($this->orderIsPaid($order)) {
        $this->assignLoyaltyPointsToCustomerFromOrder($order);
    }
}

private function calculateAndApplyOrderPromotions(Order $oder): void {
    $this->promotionApplicator->apply($order);
}

private function orderIsPaid(Order $order): bool {
    return $order->paymentState === 'completed';
}

private function assignLoyaltyPointsToCustomerFromOrder(Order $order): void {
    $this->loyaltyAssigner->assign($order);
}
</code></pre>
<p>This should be way easier to read. In the new version we even have extra information about what is happening, namely: Assigning loyalty points to a customer. We could rename the <code>loyaltyAssigner</code> to something like a <code>customerLoyaltyAssigner</code> but to me this doesn't make it allot better. I don't want to deviate from the names to much, because the class of the loyaltyAssigner is named LoyaltyAssigner. So naming it similar can be pretty beneficial for readability and understanding the code. One note, if the <code>orderIsPaid</code> can be added to the <code>Order</code> class that would be better, but in this example we assumed <code>Order</code> is immutable for us.</p>
<h3>Restructuring</h3>
<p>Even with all naming correct and clear, a program can still makes no sense because of a wrong structure. Even a good bedtime story will be complete gibberish when you start midway and jump around from chapter to chapter. Generally you'd want to have a structure which tells your story from the start till the end while keeping it simple possible. You can achieve this by trying to explain, in words and without looking at the code, what a function is supposed to do. If the code follows the same story, good job. If not try and restructure it. Can't you tell the story without looking at the code? Your function probably does to much, try and cut it up in smaller functions.</p>
<p>Let look at a small but exaggerated example.</p>
<pre><code class="language-php">/**
 * A user is always allowed if it is an admin
 * For running locally you must be an admin
 * Otherwise check the resource owner against the user
 */
public function allowed(User $user, Resource $resource): bool {
    if ($user->ip !== '127.0.0.1' &#x26;&#x26; $user->role !== 'admin') {
        return $user->id !== $resource->user_id;
    }

    return $user->role === 'admin';
}
</code></pre>
<p>Clearly from the descriptive comment the code is. But it doesn't follow the same narrative? I'd say: yes, we can. Lets restructure the code such that all edge causes are clearly visible.</p>
<pre><code class="language-php">public function allowed(User $user, Resource $resource): bool {
    if ($user->role === 'admin') {
        return true;
    }
    if ($user->ip === '127.0.0.1') {
        return false
    }

    return $user->id !== $resource->user_id;
}
</code></pre>
<p>Now it follows the narrative more closely and we made all edge cases visible, while the 'general' case is at the end. Of course we can go further and introduce some variables to make it even better, but that is besides the point. Another easy way of restructuring code is bringing edge cases more on top and make return clauses simple. This way it is easier to read and explain. Nobody can explain a function whom returns a composition of multiple conditions.</p>
<h3>Refactoring</h3>
<p>Sometimes a minor restructuring or renaming doesn't do much. Or you end up with so many private function which doesn't do the readability justice. In that case you should consider a refactor. Where you split up different parts in separate files / classes or other units. Don't be afraid to introduce a value class of two, it will make it more readable.</p>
<h3>Explanatory Comments</h3>
<p>As a last resort you can add a comment. Why as a last resort? Well every line of comment is a part a non-functional part which you need to maintain besides the code. But don't comment on what the code does, that should be said by the code itself. Tell why it does it. Or with what algorithm. This provides extra context instead of explaining the code in an other language.</p>
<p>As an example, imagine you have a prime number generator based on the Sieve of Eratosthenes. You could explain the whooole algorithm in a comment. But.. Does that do it justice?</p>
<p>What I think is cleaner, write to code as clean as possible, add a comment where you reference the algorithm used and provide a online resource which explains it. This way the code is as clean as possible, and if someone would want to debug / change the code, they have a good enough lead to start gathering information and understanding your code.</p>
<h2>Read; Comment; Rewrite</h2>
<p>So we know what tools we have, but knowing when to use them is not easy. Not to worry, I got a easy starting out strategy. With it you can get a feeling and over time you will start rewriting your code less and less.</p>
<p>Write your code, as you would. Re-reading the code and think what you'd want to clarify or how you would explain it. You can even write it out in a temporary comment if it helps you. Now start rewriting your code with the tools above to incorporate as much of the explanation as possible in you code. Lastly, remove the comment because it is now redundant.</p>
<p>Most of the time it is fairly easy with just some variable renames. But sometimes you will need to restructure the code, put things in private function to clarify the behavior.</p>
<h2>Liked what you read?</h2>
<p>I hope this whole tirade was informational for people, this was my view on writing readable code. There are, of course, many other views on this subject, so don't shy away from reading other people's thoughts. For me books like 'clean code' by Robert C Martin and The Art of Readable Code by Dustin Boswell and Trevor Foucher were a very good resource to get more grip on writing readable code.</p>
<p>Anyway, happy coding!</p>


Have you ever read code from your past self or an open source package and thought "What does this code do?" over and over again? Well you are not alone, but there are things you can do to improve the readability and maintainability without littering the code with pages of documentation comments.

Tips for Readable code

<p>Bear in mind, this post reflects my experience and opinion. If you don’t agree, that is fine. My point of view should still give you a good resource for how to write better comments.</p>
<h2>The good</h2>
<p>Let’s start simple, why are comments good? Comments should make your code more readable and this is really important. Most programmers read more code than they write. When you are tracking a bug, adding features to existing code or reworking code. You will need to read a lot of code. So our main goal with comments, should be to make your code easier to read.</p>
<p>So a small summary above a function or a small part of code can be really handy. You can read the comment, and continue.</p>
<h2>The bad</h2>
<p>Let's take a look at the flip side of the coin, why are comments all that bad? Well first. People just over do it. Reading every, reading every, part of a, part of a, sentence, sentence, twice is, twice is, VERY ANNOYING. You see what I did there? I see this actually a lot. Take a look at the code sample below as an example what I mean. Every line of comment in there could be read from the code alone. All comments are completely redundant and mirror the code. All comments duplicate what you can already read. Just like the last three sentences. And when you read a lot of code, it just becomes a nuisance.</p>
<pre><code class="language-php">/**
 * A customer
 */
class Customer
{
    private string $name;
    private array $orders;

    /**
     * Returns the name of the customer
     * @return string
     */
    public function getName(): string
    {
        return $this->name;
    }

    /**
     * Gets customer's loyalty points by summerizing the customer's
     * order loyaltypoints
     * @return int
     */
    public function getLoyaltyPoints(): int
    {
        // start loyalty points to 0 and use it to sum
        $loyaltyPoints = 0;

        // Loop over orders to sum the order's loyalty points
        foreach ($this->orders as $order) {
            $loyaltyPoints += $order->getLoyaltyPoints();
        }

        // Return sum of orders of loyalty points
        return $loyaltyPoints;
    }
}
</code></pre>
<p>But what is really the issue, if you have a good highlighter you can just skim over these comments. Or over the code. But comments actually have multiple downsides. So first the least compelling argument: comments take away space which could be used by code. It makes your code waaaay bigger.</p>
<p>But more important: Comments are not code, and it makes working with your code harder. Every change you make, you will need to check if all the comments in the code around it are still relevant. What’s more, if someone forgets to update the comments, the comments will tell your colleagues or the future you a different story than the code. Which is annoying if you actually (have to) use the comments to skim over code.</p>
<p>And lastly, switching context is hard! Whenever you want to read it all, or start ignoring comments. You need to switch context between, reading a programming language and reading (or ignoring) a human language.</p>
<h2>The ugly</h2>
<p>Now, what can be said more? Well structurally commenting will make your code more ugly! I see this sometimes were people write incomprehensible code, put a comment above it, and call it a day. Remembers comments is not code, if someone changes the incomprehensible code without changing the comment, you will have a really bad time. To illustrate this, let's take the <code>getLoyaltyPoints</code> function from the earlier example and make the code smaller, but in my opinion: worse</p>
<pre><code class="language-php">...
    public function getLP(): int
    {
        // start loyalty points to 0 and use it to sum
        $lp = 0;

        // Loop over orders to sum the order's loyalty points
        foreach ($this->all as $o) {
            $lp += $o->getLP();
        }

        // Return sum of orders of loyalty points
        return $lp;
    }
...
</code></pre>
<p>One last caveat. There is one exception: Optimized code. Within some code-bases you need to get the absolute best performance out of your code. Performance optimized code just isn’t the most readable, so a comment here and there will be useful.</p>
<h2>Conclusion</h2>
<p>So I hope this gives you some thinking material. I have written a <a href="/blog/2021-02-19-tips-for-readable-code">follow-up post</a> about how to write more readable code, in which I also cover when to comment. But after reading this, you should be well on your way to think more critically about comments. The main three takeaways are:</p>
<ul>
<li>Don't just add comments because of convention or because you can.</li>
<li>Don't justify a comment for bad code, or the other way around. Just write better code.</li>
<li>Do start thinking, when you want to write a comment. Chances are you can change the code such that you won’t need the comment.</li>
</ul>
<p>To prove my point, the code below have ZERO comments and I think it doesn't need it.</p>
<pre><code class="language-php">class Customer
{
    private string $name;
    private array $orders;

    public function getName(): string
    {
        return $this->name;
    }

    public function getLoyaltyPoints(): int
    {
        $loyaltyPoints = 0;

        foreach ($this->orders as $order) {
            $loyaltyPoints += $order->getLoyaltyPoints();
        }

        return $loyaltyPoints;
    }
}
</code></pre>


This statement seems really controversial, early on in my career I got told that every function should have a comment and commenting makes your code more readable. Now I am going to tell you why it really isn’t.

Why comments don't make your code more readable

<p>So I got in on the new hype nowadays: Statically generated websites with a JAMstack. My reason for it is twofold, I wanted to learn about this new hype. But more importantly, I didn't want to maintain my WordPress, I don't want to update it and it's plugins to keep it secure, I don't keep updating a template in order to keep my website viewable throughout updates and most importantly I don't want to receive emails because some Russians tried to log into my WordPress account or fear it got hacked because I didn't update it quickly enough.</p>
<h2>Static... what now?</h2>
<p>So first, a short introduction what this statically generated thing I am talking about?</p>
<p>With WordPress your content, your pages, blogs, menus, are stored in a database. For each page access WordPress will roughly do the following:</p>
<ol>
<li>Consult it's database and check what kind of page the user tries to access.</li>
<li>Fetches all the content from the database</li>
<li>Puts the content from the database in the template</li>
<li>Renders the page which the content</li>
<li>Serve the generated page to the user</li>
</ol>
<p>With statically generated websites step 1 trough 4 are done when you build the website, before you upload your website. Now your websites is just a bunch of HTML pages without the server needing to do anything for you, just like the old days. The benefits: Less dependencies on external parties, no need of a PHP capable web host, a website which is easy to cache and the best thing: it is fast as heck.</p>
<p>To be fair, blog type websites or just plain old websites do lent themselves very well for this thing. Every type of website where you don't need any input from the end user and  where you can have your content ready before-hand and this content isn't changed much. You can also make more complex sites static, for example webshops. It's just not so straight forward.</p>
<h2>This is the way</h2>
<p>So how did I did this, what did I use? And how did I like it.</p>
<h3>Content management</h3>
<p>So first things first, I wanted to have all my content available in my source control. I am an developer and I don't mind tinkering when I get full control. So I looked up a CMS which is git based and I ended up with Netlify CMS. Not the best choice I can make, now I require a netlify account and an Netlify identity. But their are upsides, I can edit my content without it, and switch it out when something better comes along.</p>
<h3>Static framework</h3>
<p>So we have some options, if you google 'static website generator' you got things to choose. I ended up with NuxtJS, which is based on VueJS, I really like VueJS. It is easy to get into, it has good documentation and a good ecosystem. It has a downside though, it is not as fast as others out there, you need to have knowledge about javascript and VueJS, although VueJS is easy enough to get into and lastly my biggest issue, the javascript ecosystem is really unstable and I still need to apply updates every week. Luckily even I know allot of javascript (I ended up using typescript, because why not?) and even if I don't update, my site is static, so no security issues there!</p>
<p>There even is a create template for NuxtJS and I got the basics up and running within half an hour. Whats more, I got some content loaded within have an hour. Amazing!</p>
<h3>TailwindCSS</h3>
<p>But... I got no styling, I could have used some front-end frameworks like Bootstrap or Bulma and purchase a template. But... I wanted full control and I wanted to learn something new, so I used TailwindCSS. I can recommend it is you want the freedom, you know some CSS and you go FULL rage when CSS promises you to do a thing while it obviously doesn't work for this specific instance. In my opinion, TailwincCSS makes CSS simpeler, but you still use CSS, thus it is not as easy as Bootstrap.</p>
<h2>The struggles</h2>
<p>So this is a more technical solution to WordPress, you still need to have some coding skills to do this. In my opinion with basic HTML and JS you will be fine. What's more, if you need more complex things, like tags on your blogs, you need to build it yourself. No easy plugins or database joins, at least I didn't find any.</p>
<h2>Final verdict</h2>
<p>To be totally honest, when I started I thought I wouldn't like the hassle and end up buying something like a squarespace account and be done with it. I just want a website to have a presence and to blog a bit.</p>
<p>But! It was way easier than I thought, and even though I don't like netlify CMS that much, I like the freedom that the whole stack brings me. I will switch CMS one day, or just inline edit in NuxtJS (because yes it can do that in dev mode).</p>
<p>All in all, a fun experience and this website is here to stay! 10/10 would statically generate it again</p>


My journey migrating from WordPress to a fully statistically generated with NuxtJS, TailwindCSS and Netlify CMS, aka a JAMstack.

Going static

<h2>Trees?</h2>
<p>But let’s begin at the beginning. Within computer science, a tree is a data structure containing nodes. Each node in the tree contain information and can refer to other nodes in the tree, these are known as children. Each node without child nodes is called a leaf node. When you draw this out with pen and paper and squeeze your eyes real close, you might see the tree-like structure in it (or you might need another beer).</p>
<h2>Soo B what?</h2>
<p>Some people might confuse a B tree with a binary tree and those people are not far off. Binary trees have one key value per node and have two children. When looking up a value you start traversing the tree, beginning with the first node (which is known as the root node). If the value is smaller than the key of the node you take the left child, if it is larger you take the right child. When the lookup value matches the key of the node, that is the node you were looking for. This way value lookups in a balanced tree are only O(log n). Of course this can be made so that each node has one or multiple data items per key value.</p>
<p>The B tree on the other hand has not one key value per node but a predefined amount of sorted key values, known as the bucket size. This means that it also references more children nodes, in fact each node references maximal its bucket size plus one child. This whole bucket thing will however increase the steps it would take to lookup a value in the most optimal situation. So why not just use a binary tree, since that is theoretically faster? Well, with a binary tree you need to jump around in memory and this comes at a great cost, which is why B trees tend to perform better.</p>
<p>Moreover when implementing a B tree which also writes its nodes to disk, you save a lot of disk IO by clustering the keys and nodes. Each node means potentially another disk operation and those tend to be one of the slowest types of operations. One might ask: “If disk operations are that slow, why not add all keys to a single sorted list and iterative lookup the value?”. First off good question, but this does mean that you potentially need to iterate the whole list to find a key value and on top of that it means that the whole list needs to be in memory and mutating a large list is quite expensive. So it is important that a good balance is chosen between between disk IO and operations. Common bucket sizes are 64 keys, but this may vary based on the memory and cache size of a system. Ideally you want a whole bucket to fit in your cache.</p>
<h2>There was a + right?</h2>
<p>So how does a B+ differ from a B tree? Well a B tree and binary tree have the values which correspond to the key value of the node in the node itself. B+ trees on the other hand store all the values in the leaf nodes. This has as benefit that deleting and inserting is a bit easier and on top of that, when the leaf nodes reference their neighboring leaf nodes, iterating over all values will be faster.</p>
<h2>Why?</h2>
<p>To understand why, let me give a little example. Given we have a document store, where we have n documents. These documents need to be stored and filed such that we can refer to a document by an identifier so that we have easy access to that document. In this example the identifier is our key and the document is our value, when we create a B+ tree of these documents we can delete, insert and find documents with relative ease. The problem using other structures as hashmaps is that these structures are not as dense as B+ trees. More over, dynamically growing hashmaps becomes quite expensive very fast and let’s not start about the trouble one will get into when trying to create a disk based hashmap.</p>
<h2>Advanced topics</h2>
<p>Now we know what a B+ tree is, let’s start looking into how lookups, inserts and deletions are performed.</p>
<h2>Key Selection</h2>
<p>The easiest of the three are the lookups. As mentioned before, in order to find a given key in a given B+ tree we need to traverse the tree starting with the root node. However when comparing the given lookup key with the keys in the bucket, when do we decide to go to the node of that key? Let me first note that there are multiple ways to do this, but I will explain and use the following rule. For every key in the bucket you compare it with the keys in the bucket and you choose the first node where the key in the bucket is bigger than the lookup key. When every key in the bucket is smaller than the lookup key, the last node is taken.</p>
<p>This is done recursively until a leaf node is found, where the data item belonging to the given lookup key is returned.</p>
<h2>Insertion</h2>
<p>The initial insert of a given data item and key is fairly easy. First the leaf node which will hold the key and data item must be found, this is done with the previously mentioned key selection algorithm. Next the key is inserted in the bucket at the appropriate place within the bucket. If the bucket is full after the insertion, the node is split where one node has the lower half and one node the upper half of the keys. Now the newly created node must be inserted in the parental node and if needed that node can be split as well.</p>
<h2>Deletion</h2>
<p>The hardest algorithm is deletion, in fact this is such a pain to implement that most B+ tree implementation use a small trick to do this. Upon deleting an item, mark the key as invalid and after a defined amount of deletions rebuild the complete tree from ground up. This seems insanely slow, but in fact the amortized complexity is the same.</p>
<h2>Bulk insert</h2>
<p>Building a complete B+ tree given a sorted set of key-value pairs is quite simple to do. Start by dividing the sorted key value pairs in parts such that each part fills a bucket, but leave one space empty for a future insert. Create leaf nodes for every part and fill the buckets with the given data.</p>
<p>Now our new dataset consists of the leaf nodes containing our key value pairs, now nodes can be created where each key is the highest value in our leaf node’s bucket. This continues until we end up with just one node.</p>
<h2>To conclude</h2>
<p>This concludes the B+ trees, as example one might look at HybreDb – B+ tree. HybreDb is the project I talked about at the beginning of this post and it does implement the above described B+ tree. Only the deletion I used is a bit more complicated as well as the disk based B+ tree, which allows the whole tree to be written to file and all changes are appended to a file.</p>


Since I have been busy with a new project for school and since it seems promising, let’s talk more about it! As can be guessed by the title it is a database. And as people might know B+ trees are one of the most important parts of a good database. Datastores, key-value stores, relational databases, graph databases all have a B+ tree or at least a B tree. These trees are data structures that are used to store and lookup key values within databases.

On databases: B+ trees

<p>A few weeks ago I needed to create a way of deploying webservices in nodeJS for a client of mine. I looked at some of the existing packages out on the web, but I couldn’t find anything to my liking. I decided to custom build it, not only for learning purposes, but also to be able to use a framework the client was already accustomed to.</p>
<p>One of the problems I faced was the URL routing. Of course there were no problems with static routes, but one of the nice things to have in these kind of situations is parameters within the URL and other fancy things like wildcards. Once again I turned to the web, but the only given solution I found was “just regex all routes and per request iterate over all route regexs”. Although this will work, it isn’t a really elegant approach, I even dare to say that this is almost as brute force of a solution as it gets.</p>
<p>In this post I will use the following routes (and syntax) as an example. The routes are the key within the JSON, where the accepted HTTP verbs are prepended between square brackets. The resource (a file containing the webservice) is the value in this map.</p>
<pre><code class="language-js">var routes = {
    '/': 'index.js',
    '[GET]/test/{id}/': 'test.js:paramExample',
    '[GET]/test/{1}/{2}/': 'test.js:paramExample',
    '/test/hallo/world/': 'test.js:halloworld',
    '[GET,PUT]/test/json/': 'test.js:getJson',
    '[POST]/test/': 'test.js:post',
    '/statics/*': 'statics.js',
}
</code></pre>
<h2>Tree building</h2>
<p>Ok, of course we could regex the whole thing, but let’s first use our brains. We need a way to structure all routes given. I have done this by creating a tree structure which can be seen in te figure to the right. Every purple node is a node which is bound to a resource, so those are possible end nodes. The once with curly brackets are parameters and the astrix is a wildcard. The HTTP verbs are not seen in this picture, but can still be present in the actual node structure, I choose not to show them to allow for a cleaner representation.</p>
<h2>Tree traversing</h2>
<p><img src="/uploads/roadieroutegraph-300x271.png#right" alt="Routes structured in a tree where each purple has a resource bound to it"></p>
<p>Routes structured in a tree where each purple has a resource bound to it</p>
<p>For the people that read my previous post about search algorithms, this will look awfully familiar to a state space representation. In fact it can be used as such, we can use the created tree as possible paths. If we have an input URL we can traverse the tree in that order. Say we have ‘/test/hallo/world/’ the order of traversing will be ‘/’->’test’->’hallo’->’world’, great this works! Except for an URL like ‘/test/hallo/’, with the given routing table we would like to end up as a ‘/test/{id}/’ route, but in our implementation it will end up at ‘/test/hallo/’ which does not have a resource bound to it. So in fact, we need a search algorithm to solve this.</p>
<h2>Searching the answer</h2>
<p>Before anyone tries an uninformed search algorithm let’s revisit our tree. We now know that all purple states are goal states if and only if the HTTP verb matches and the complete user’s route is used — wildcards use up the complete left-over route. When we try an uninformed search algorithm for ‘/test/json/’ it will map to ‘/test/{id}/’ before ‘/test/json/’, this is because we need to apply a kind of ranking in our routes. We could restructure our whole tree to make sure the static routes are looked at first, than the routes with parameters and lastly the wildcards. But instead of restructuring the whole tree with every added route, we could also add weights and use a informed search algorithm.</p>
<p>So our weights are as followed: [1]:static, [2]:parameter, [3 times the size of the leftover URL]:wildcard. I know the wildcard is the ugly duck in this case, but I will explain that later. Now when we use greedy search — which always takes the cheapest route first, ‘/test/json/’ will in fact be routed to ‘/test/json’ instead of ‘/test/{id}/’, this is because ‘/test/json’ as a total cost of 2 and ‘/test/{id}’ has a cost of 3. Now the wildcard, we always want the static routes first and the parameters after that, say we have a ‘/{1}/{2}/{3}/’ route and a ‘/*’ route. The parameter route has a cost of 6 (2 for each parameter), in fact the maximum cost of any route containing only static and parameters is 2 times the length of the URL items. Therefore if we want the wildcards to be last, we need to scale according to the left over URL parts, we could suffice with 2n+1 but anything greater than 2 times the URL items is good, and with 3 times the URL items you have some space to apply ranking between the wildcards themselves.</p>
<h2>Worth it?</h2>
<p>Hell yeah! The main problem with regexing everything is that your worst case scales according to the total of routes you have. This thing scales with the size of the user route, because shorter URLs need to check less states before reaching their goal state. Of course this model can be expanded to include some kind of regex mechanism inside each node, typed parameters, ect. Also a thing to note is that adding or removing routes is really easy. Just add a node per URL part if it doesn’t exist yet and add a resource to the end.</p>
<p>See a live example in the nodeJs roadie package, available on <a href="https://www.npmjs.com/package/roadie">npm</a> and <a href="https://github.com/blackshadev/Roadie">github</a></p>


Ever wondered how packages like flask and express route their URLs to the correct functions, even with properties like wildcards and parameters? In this post I will discuss a solution to this URL routing problem which uses a search algorithm to find the correct route.


URL routing

<h2>Problem description</h2>
<p>Search problems are quite common, for example. A maze solver, a puzzle solver or it’s most common use: a path finder. All search problems can be described as a tree, where each node represents a “state”, to advance from one state to the next we use what is called a “move”. Some of these states are a goal states, these are what we are looking for and preferably as fast as possible with the shortest cost.</p>
<h2>State space of a maze</h2>
<p>Given a random maze with one exit and one entry. Each state consists of the position within this maze. The path from a given state is given by going up in the state tree. The exit is marked as a goal state and a move will return all possible follow-up states from a given state. Immediately it can be seen that if the maze has loops and we expand all states as deep as possible we would end up in an endless loop at some point.</p>
<h2>Traversing the state space uninformed</h2>
<p>Now we have a way of representing the problem in an uniform matter, the only thing left is to find is a method to get to the goal state(s).</p>
<h2>Depth first</h2>
<p>Let’s begin with the most simple one: Depth first search. This search algorithm expands all states as deep as possible, so if the maze has loops this isn’t the best idea, but it is a start. If we wanted we could build a safe guard into the move function to not allow the occurrence of the same state within a branch of the state space twice, this is referred to as branch closing. The reason depth first search is so easy is because we have to only keep track of one branch at a time, moreover it is a recursive algorithm. Below follows a simple python implementation of depth first search.</p>
<pre><code class="language-python">def DFS(state):
    if(isGoal(state)): return [state];
    states = move(state)
    for s in states:
        res = DFS(s)
        if(res != None):
            return [state] + res

    return None
</code></pre>
<h2>Breadth first</h2>
<p>Breadth first search is a more memory heavy search algorithm, what it does instead of diving into the depth of our state space we expand horizontal first, this way we search all possible states and this way we avoid being stuck on those loops. More importantly is this will always return the shortest path, this is because instead of deeping out, we expand every possible path one step at a time. Note, again we could close some tree branches based upon reoccurring states, but for simplicity sake this is left out.</p>
<pre><code class="language-python">def BFS(start):
    queue = [[start]]

    # branch is one branch of the tree, it contains states
    branch = None
    while len(queue) > 0 :
        branch = queue.pop(0)

        if isGoal(branch[-1]): break;

        states = move(s[-1])
        # add all follow-up states to the queue
        queue = queue + [ [branch + s] for s in states ]
    return branch
</code></pre>
<p>As it can be seen, we need to keep track of every branch we create, this can lead to an immense consumption of resources.</p>
<h2>Just think before you act</h2>
<p>Now let’s assume every move has a cost associated with it, this cost is given in the form of a positive number and with this cost we create a weighted graph. Instead of traversing everything let’s try and think which states will likely give us the best result. For these examples the move function will not only return the possible states, but also the cost to get there associated with them.</p>
<h2>Dijkstra</h2>
<p>The first thing anybody would think of is, just expand the path with the lowest cost so far. And indeed this is a valid method. This algorithm is called after Edgar Dijkstra who invented and showcased this algorithm in the early days of the computers. Now an important side note, within Dijkstra’s algorithm it is specified that we can’t have reoccurring states in our path, so we will apply that within our example as well.</p>
<pre><code class="language-python">def dijkstra(start):
    queue = [{"cost": 0, "path": [start]}]

    branch = None
    while len(queue) > 0:
        branch = queue.pop(0)

        if isGoal(branch["path"][-1]): break;

        states, costs = move(branch)
        queue = queue + [ {
                "cost": branch["cost"] + costs[i],
                "path": branch["path"] + states[i]
            } for i in range(len(states))
            if states[i] not in branch["path"] # ignore already present states
        ]
        queue = sorted(queue, key=lambda x: x["cost"])
</code></pre>
<p>The example above is kept simple, instead of resorting the whole queue we could insert the states on the correct position to keep everything sorted, but this is easier to read. As can be seen we also keep track of the whole path again, but we prioritize the expansion of paths with a lower cost. Some observant readers will see that when every cost is the same, we will have the same behavior as breadth first search.</p>
<h2>A* the star of search algorithms</h2>
<p>For the most search problems we have some sort of measure for how far we are away from a end point. Lets call this our estimate and this can be calculated for every state. In our maze example this can be the absolute distance between us and the exit. If we now prioritize the expansion of states to the states with the lowest cost and estimate, we end up with searching the least possible amount of states and finding the optimal solution first.</p>
<pre><code class="language-python">def AStar(start):
    queue = [{"cost": 0, "estimate": estimate(start), "path": [start]}]

    branch = None
    while len(queue) > 0:
        branch = queue.pop(0)

        if isGoal(branch["path"][-1]): break;

        states, costs = move(branch)
        queue = queue + [ {
                "cost": branch["cost"] + costs[i],
                "estimate": estimate(branch["path"][-1]),
                "path": branch["path"] + states[i]
            } for i in range(len(states))
            # ignore already present states
            if states[i] not in branch["path"]
        ]
        queue = sorted(queue, key=lambda x: x["cost"] + x["estimate"])

    return branch
</code></pre>
<p>As can be seen, this is really a small alteration to dijkstra’s algorithm.</p>
<h2>End remarks</h2>
<p>And this concludes our tour through search space, the given examples are not ultimate solutions and are only there as a guide to explain the algorithms. Also there are lots more search algorithms, but these are the most used and most essential algorithms, basicly if you can reduce a problem to the state space you have a good way of reaching your goal. On top of that, if you have a good estimate function for your state space you have a really really great way to reach your goal with A*. Most of todays GPS programs run either dijkstra or A* to do the path finding.</p>


Search problems are one of those problems that every programmer will encounter at least once in his or her life. An important note is that this post will explain search problems, but these are not “how to lookup relative hits in multiple texts” but more “given a map, what is the best route from A to B”. I will discuss search problems in general, Astar and other search algorithms.