DEV Community: Stephanie Bergamo

Building a B-tree in Go: The gap between theory and implementation

Stephanie Bergamo — Wed, 14 Jan 2026 10:33:08 +0000

I've been obsessed with database internals lately 🤓. It started with Alex Petrov's "Database Internals": one of those books where every page makes you think "wait, THAT'S how it works?!"

But there's a gap between understanding the theory and really getting it. I could explain what a B-tree does to a 6yo, draw the diagrams and the likes. But could I actually build one? That itch needed scratching.

So I dedicated a bit of my time off coding a B-tree from scratch in Go. About 15 hours total, spread across a few days between coffee, sport, rest and debugging sessions. I definitely didn't need one for production (PostgreSQL does this infinitely better), but I wanted to really understand what happens when I type CREATE INDEX.

And honestly? It was one of the most fun coding challenges I've done in a while.

What's a B-tree, anyway?

If you've used a database, you've used a B-tree: they're the data structure behind most database indexes. The key insight: unlike binary trees where each node has 2 children, B-tree nodes can have many children (determined by the "order"). This makes them perfect for disk storage where reading a block is expensive.

I won't explain B-trees from scratch here: Alex Petrov's book does that brilliantly. If you're not familiar with the basics, start with chapter 2 of Database Internals. This article assumes you know what a B-tree is and focuses on what I learned building one.

The Implementation: Easy, Interesting, and "Wait, What?"

The Easy Part: Search

Binary search within nodes, recurse to children. With good tests, this was maybe 2 hours including edge cases. The satisfying kind of easy where you know exactly what to do.

The Interesting Part: Split

Understanding why nodes split (keep tree balanced) vs how to split them (median, two halves, promote) took some head-scratching. Drawing it out on paper helped.

The surprise: root splits are special. You create a brand new root with just the promoted key. The tree grows taller, not wider.

The "Wait, What?" Part: Cascade

Oh wow. This is where I learned the difference between "I understand B-trees" and "I can build a B-tree."

When a split cascades up, you're not just inserting a key: you're managing a whole graph of parent-child relationships. Split an internal node? Better redistribute its children too. And update every child's parent pointer. Miss one? Silent corruption. The debugging session was ...fun...

The full implementation is on GitLab, but the key insight was: when you split an internal node, you're not just moving one or two keys: you're rewiring an entire graph. Get one pointer wrong and your tree silently corrupts. Tests caught this. A lot. And when they didn't and I had to discover that by myself, I wrote new tests to confirm and made sure I fixed the bug.

What Building It Taught Me (That Reading Didn't)

B-tree vs B+tree: Not Just Academic

I knew the theory: B-trees store data everywhere, B+trees only in leaves. But implementing it made me feel the difference.

In my B-tree, search can stop at any level when it finds the key. Elegant! But range scans would be a nightmare (you'd have to traverse the entire tree structure). B+trees sacrifice that early-stop elegance for better range queries (linked leaves).

Now when I see PostgreSQL using B+trees for indexes, I get why, not just what.

Sequential inserts are... weird 🤔

Testing with INSERT 1, 2, 3, 4... created a hilariously unbalanced tree: 7 levels deep with just 50 keys, all growing to the right.

Random inserts? Beautiful 3-level balanced tree.

This is why databases have bulk loading strategies and why REINDEX exists. Seeing my skewed tree made me appreciate those optimizations viscerally.

TDD Isn't Optional (or at least not for me anymore)

I've been building software with TDD for so long now that coding without tests feels... naked? Uncomfortable? Like I'm missing something fundamental.

Could I have built this B-tree without tests? Sure. Would I have shipped a dozen subtle bugs? Absolutely.

Writing tests first isn't about following best practices anymore: it's how I think through implementation. The test tells me what "done" looks like before I start coding.

For this project, that discipline caught:

Duplicate key insertion (oops, forgot to check)
Index out of bounds on edge cases (classic off-by-one)
Children count mismatch after splits (n keys → n+1 children, remembered that in the test)
Parent pointers pointing to the wrong parent (caught by checking parent relationships in tests)

When cascade finally worked and all 20+ tests turned green simultaneously? That's the confidence TDD gives you. I wasn't hoping it worked: I knew it did. That's the payoff: shipping with certainty, not crossed fingers. (by now I guess you might have understand that I'm a strong believer in the increased productivity and overall quality TDD is bringing).

And yes, 100% coverage throughout. Some call it obsessive. I call it professional 😇.

The "It Just Clicked" Moment

There was this moment, probably 10 hours in, debugging why searches failed after cascade. I was staring at my tree visualization (can't help but thanks Copilot for that helper function!), and suddenly I saw it: the children weren't following their parent after the split.

That moment when the entire structure suddenly made sense (not just conceptually, but in memory, pointers, the whole graph of relationships) that's what hands-on gets you. No amount of reading gives you that.

The Numbers

Time: ~15 hours across 4 days
Code: ~200 lines of implementation
Tests: 20+ unit tests, 100% coverage
Bugs found: Too many to count (but TDD caught them all)
Coffee consumed: Significant

What's Next

This was way more fun than I expected. There's something deeply satisfying about implementing a data structure you've used for years without really understanding it.

Next up: LSM-trees (Log-Structured Merge trees). They represent the opposite tradeoff: B-trees optimize for reads (in-place updates), LSM-trees optimize for writes (append-only). Understanding both will show me why Cassandra chose LSM while PostgreSQL chose B+trees.

Reading about compaction strategies is one thing. Implementing them will be another level entirely 🤩.

If you're curious about database internals, start with "Database Internals" by Alex Petrov. Then pick something and build it. The gap between reading and implementing is where the real ~magic~ learning happens.

You can see the full implementation on my self-hosted GitLab (yes, I run my own instance: infra nerd life). Pull requests welcome if you spot ways to improve it! 😊

Hugo.io - Multiline cells in a table

Stephanie Bergamo — Fri, 10 Jun 2022 07:22:26 +0000

A problem

Building table in markdown is super easy and well-documented.

However, having a bit of formatting within it, like carriage return within a cell as below is not possible by default.

Hugo uses Goldmark (a CommonMark implementation in Go) to process the markdown. Apparently it's extremely fast, with this implementation we choose to block any HTML processing d'HTML by default.

A solution

Once you know this, solving this is pretty straightforward.

You can customize plenty of Goldmark options in the configuration file (config.toml/yaml/json).
So what we want to do is autorising Goldmark to render HTML content :

[markup.goldmark]
    [markup.goldmark.renderer]
    unsafe = true

From now, within the table, we just need to add <br> tag as below :

|Adresse | Parking de La Poste<br> Le Bourg <br>97122 Baie-Mahault |

That's it !

Free tips

If you don't want to bother with | when building tables, someone very nice has built a table generator.

We thank this person, from the bottom of our heart 💜.

Testing with Kotlin and JUnit5

Stephanie Bergamo — Fri, 10 Jun 2022 07:10:53 +0000

The problem

I've recently started coding backend and mobile stuff in kotlin, following a book, then starting a pet project, ...

In the meantime, I've also started to gain a lot of interest on Test Driven Development and found myself wondering "wow, how do I test in Kotlin ? which framework should I use?"

To learn further, I've deciced to start a serie of articles on this topic:

Basic testing in Kotlin with JUnit5 from the Java ecosystem (this article)
Basic testing in Kotlin with Kotest built for kotlin specificatlly (upcoming)
Mocking, stubbing and contract testing in Kotlin with JUnit5 and Kotest (upcoming)
A comparision of these two testing frameworks (mostly in term of features, usability, readability), this one might be a bit opinionated. (upcoming)

I'm a java-ist so my go-to test framework is JUnit, this is the sole reason why I'm starting by this one.

Agenda

Getting started
Execution and lifecycle
A very simple test
Checking exceptions
The power of parameterized tests
Conditional tests
Conclusion

If you just want to jump in the code, please yourself

Basics on testing with JUnit5

Setup

For the Gradle users, here's the setup.

To be able to use the JUnit5 features, we must first add the dependencies:

  testImplementation("org.junit.jupiter:junit-jupiter-api:5.8.2")
  testImplementation("org.junit.jupiter:junit-jupiter-engine:5.8.2")

Then we must specify we want to use JUnit to run the tests :

// For Gradle + Groovy 
tasks.test {
    useJUnitPlatform()
}
// For Gradle + Kotlin 
tasks.test {
   useJUnitPlatform()
}

The entire necessary configuration can be found here.

Note: I'm using gradle 7.3.3.

Tests execution and orchestration

Junit will consider as a test any function annotated with @Test, @RepeatedTest, @ParameterizedTest, @TestFactory, or @TestTemplate.

We also have annotation to help us wrap test execution:

@BeforeAll executed first, before the whole test suite. useful for instiantiating external dependencies for instance.
@BeforeEach executed after BeforeAll and before any test, useful when we need to ensure the state is clean before launching for example.
@AfterEach not surprisingly, executed after any test.
@AfterAll executed at the end of the test suite, for housekeeping purpose, pushing stats or whatever.

A very simple test

Now we're all set, time to code and test!

Let's say we have a useless class like this one :

class Dollar(val value: Int) {
    var amount: Int = 10

    operator fun times(multiplier: Int) {
        amount = value.times(multiplier)
    }
}

Obviously we want to test this class has the expected behavior, with a very basic test:

We'll need to first import the JUnit5 helpers :

import org.junit.jupiter.api.Assertions
import org.junit.jupiter.api.Test

And then we can create our test as follows:

@Test
fun `should multiply correctly`() {
    val five = Dollar(5)
    five.times(2)
    Assertions.assertEquals(10, five.amount)
}

We can now execute this, using our favorite IDE or the simple gradle command :

./gradlew test

A quick word on naming

Well, no strong rule here, but a test method should :

test one thing, and one thing only
have an explicit name so the expectation is clear

You may have notice that I'm using backtick here.

This is a Kotlin capability, identifier for variable and method can use them, and although there's nothing mandatory here, I find it clearer.

What about checking exceptions ?

Ok, now we don't want to multiply our dollar by zero, so we change our code a bit, to raise an exception if this occurs.

Let's write the test first:

@Test
fun `should throw exception when multiplying by 0`(){
    val one = Dollar(1)
    assertThrows<NoMoneyException> {
        one.times(0)
    }
}

Yep, it's just that easy, okay, this does not even compile, since the NoMoneyException class does not exists. Let's create it !

class NoMoneyException(message: String?) : Throwable(message) {
}

We then update our times operator :

operator fun times(multiplier: Int) : Dollar {
    if (multiplier == 0) {
        throw NoMoneyException("Can't multiply by zero")
    }
    return Dollar(amount.times(multiplier))
}

You can run since and see the green test :)

Let's execute the same test with different inputs !

I think you'll agree, if we add more test cases, we'll be loosing readability and we'll duplicate the same test again and again.

Grouped assertions

Well there's a few great Kotlin assertions that comes with Junit, let's play with assertAll and a collection with a multiplier and the expected result.

@Test
fun `should multiply using stream`() {
    val five = Dollar(5)
    val inputs = arrayListOf(
        arrayListOf(2, 10),
        arrayListOf(3, 15),
        arrayListOf(10, 50)
    )
    assertAll(
        "should provide the expected result",
        inputs
            .stream() // Remove this line and use the collection directly
            .map {
                { assertEquals(Dollar(it[1]).amount, five.times(it[0]).amount) }
            }
    )
}

Parameterized tests

Well, I've used a lot of Table Driven Tests in golang, this is super helpful to write compact and repeatable tests.

With JUnit, we can achieve the same with Parameterized tests.

Parameterized tests makes tests more readable and avoid duplicates, but don't take my word for it, let's code !

First, we'll need to add a new dependency :

   testImplementation("org.junit.jupiter:junit-jupiter-params:5.8.2")

Now let's replace our previous example and use a CsvSource with the multiplier and the expected value :

@ParameterizedTest(name = "multiply {0} by 5 should return {1}")
@CsvSource(
    "2, 10",
    "3, 15",
    "10, 50",
)
fun `should multiply correctly`(multiplier: Int, expected: Int ){
    val five = Dollar(5)
    Assertions.assertEquals(Dollar(expected).amount, five.times(multiplier).amount)
}

So basically, we :

add the @ParameterizedTest annotation and optionnally define a name,
add the annotation for the the type of argument source we want to provide (@CsvSource here) with the related test cases
enjoy !

You may have noticed the name of the test? Well, this little trick makes our test super explicit and easier to debug, see for yourself :

With that, you can directly see which testcase fails, see for yourself:

I don't know about you, but I personnally find it more readable than the group assertions.

For more info about customizing the display name, see this part of the JUnit documentation.

Another nice thing, is that we can use several types of arguments as inputs:

ValueSource allows to pass a list of arguments of primitive types, String and Class: useful for a testing a single argument. See an example here
CsvSource as show-cased here, we can pass an unlimited list of arguments as a string representing a CSV input
CsvFileSource same as the previous file, except we use a CSV file. See an example here
EnumSource lets you run the same test for each constant (or a selected set) of a given ENUM. See an example here
MethodSource this one is super powerful, we can basically have anything we want as input source (say a JSON or a Parquet file), process it with the MethodSource and use it to execute our tests. See an example here
ArgumentSource this one goes even further than MethodSource. With a new class, implementing the ArgumentProvider interface, you can generate input data. See an example here

We also have a bit of syntaxic sugar with @NullSource, @EmptySource and @NullAndEmptySource.

Be careful when using BeforeEach and "parameterized" or "repeated" tests

Each item of a parameterized or repeated test suite is considered as a single test.

Therefore, whatever is defined in BeforeEach will be executed before each occurence of the test source.

Say we define a BeforeEach as follows :

@BeforeEach
fun initEach() {
    println("hello I'm a test")
}

After executing should multiply correctly which have 3 rows in its CsvSource, we'll have the following output:

hello I'm a test
hello I'm a test
hello I'm a test

Do we really want to execute this test ?

JUnit comes with multiple way to decide whether a test sould be executed or not, depending of the context.

First we can totally disable a test or a class, by adding the @Disabled annotation.

In addition, we can programmatically define condition execution depending on:

the Operating System, using @EnabledOnOs, @DisabledOnOs and the OS Enum:

@EnabledOnOs(OS.MAC)
@EnabledOnOs(OS.MAC, OS.LINUX)

the JRE, with @EnabledOnJre, @EnabledForJreRange, @DisabledOnJre, @DisabledForJreRange and the JRE Enum:

@EnabledOnJre(JAVA_8)
@EnabledForJreRange(min = JRE.JAVA_11, max = JRE.JAVA_16)

system properties, with @EnabledIfSystemProperty and @DisabledIfSystemProperty

@EnabledIfSystemProperty(named = "os.arch", matches = ".*64.*")

one or multiple environment variable(s), @EnabledIfEnvironmentVariable, @EnabledIfEnvironmentVariables, @DisabledIfEnvironmentVariable and @DisabledIfEnvironmentVariable:

@EnabledIfEnvironmentVariable(named = "EXEC_ENV", matches = ".*ci.*")
@EnabledIfEnvironmentVariable(named = "DEBUG", matches = "enabled")

Note that the two singular annotations are repeatable.

a custom condition*, using @EnabledIf and @DisabledIf with a method name or its FQN (if the method is not in the same class) as string:

@EnabledIf("execAlways")
@Test
fun `something to test`(){}

private fun execAlways(): Boolean {
    return true
}

Conclusion

That's it for this first part, covering the basics on testing Kotlin code with JUnit, we can already check a lot of things with :

grouped assertions
exception check
parameterized tests
conditional tests

I hope you'll find this useful, you can find the full test implementation here.

Ingesting an S3 file into an RDS PostgreSQL table

Stephanie Bergamo — Fri, 10 Jun 2022 07:02:30 +0000

The problem

I'm using Redshift for a while now, and one feature I find particularly useful, is the ability to load a table from the content of an S3 file:

COPY table_name
FROM 's3://bucket-name/path/file.ext'
  iam_role 'arn:aws:iam::<aws-account-id>:role/<role-name>'
  region 'region-code';

Lately, I needed to do the very same thing with a PostgreSQL database, hosted on RDS.

The good news is : YES WE CAN !

The solution

Setup

AWS pre-installs (among other things) 2 extensions on our RDS :

aws_commons
aws_s3

Now, since we need to interact with S3, we simply need to run the following command, assuming
our user is a superuser or has database owner privileges:

CREATE EXTENSION aws_s3 CASCADE;

This command installs both aws_commons and aws_s3.

Okay, that was the easy part.

Well, now we have to work on the necessary IAM role for our RDS instance...and that's where we'll find the first pitfall...

Under the hood, installing the aws_s3 extension also adds an IAM role, managed by AWS (and therefore, read only for us)
to interact with plenty of AWS services.
As we can see below, the role is linked to the S3Import function :

The problem is, we can only link a single role to a function and this one does not have any access to our S3 bucket, therefore this cannot work.

In the end, even if the policy is super short in the doc, here is what we actually need :

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "s3import",
            "Action": [
                "s3:GetObject",
                "s3:ListBucket"
            ],
            "Effect": "Allow",
            "Resource": [
                "arn:aws:s3:::bucket-name",
                "arn:aws:s3:::bucket-name/*"
            ]
        },
        {
            "Effect": "Allow",
            "Action": [
                "rds:CrossRegionCommunication"
            ],
            "Resource": "*"
        },
        {
            "Effect": "Allow",
            "Action": [
                "ec2:AllocateAddress",
                "ec2:AssociateAddress",
                "ec2:AuthorizeSecurityGroupIngress",
                "ec2:CreateNetworkInterface",
                "ec2:CreateSecurityGroup",
                "ec2:DeleteNetworkInterface",
                "ec2:DeleteSecurityGroup",
                "ec2:DescribeAddresses",
                "ec2:DescribeAvailabilityZones",
                "ec2:DescribeCoipPools",
                "ec2:DescribeInternetGateways",
                "ec2:DescribeLocalGatewayRouteTables",
                "ec2:DescribeLocalGatewayRouteTableVpcAssociations",
                "ec2:DescribeLocalGateways",
                "ec2:DescribeSecurityGroups",
                "ec2:DescribeSubnets",
                "ec2:DescribeVpcAttribute",
                "ec2:DescribeVpcs",
                "ec2:DisassociateAddress",
                "ec2:ModifyNetworkInterfaceAttribute",
                "ec2:ModifyVpcEndpoint",
                "ec2:ReleaseAddress",
                "ec2:RevokeSecurityGroupIngress",
                "ec2:CreateVpcEndpoint",
                "ec2:DescribeVpcEndpoints",
                "ec2:DeleteVpcEndpoints",
                "ec2:AssignPrivateIpAddresses",
                "ec2:UnassignPrivateIpAddresses"
            ],
            "Resource": "*"
        },
        {
            "Effect": "Allow",
            "Action": [
                "sns:Publish"
            ],
            "Resource": "*"
        },
        {
            "Effect": "Allow",
            "Action": [
                "logs:CreateLogGroup"
            ],
            "Resource": [
                "arn:aws:logs:*:*:log-group:/aws/rds/*",
                "arn:aws:logs:*:*:log-group:/aws/docdb/*",
                "arn:aws:logs:*:*:log-group:/aws/neptune/*"
            ]
        },
        {
            "Effect": "Allow",
            "Action": [
                "logs:CreateLogStream",
                "logs:PutLogEvents",
                "logs:DescribeLogStreams"
            ],
            "Resource": [
                "arn:aws:logs:*:*:log-group:/aws/rds/*:log-stream:*",
                "arn:aws:logs:*:*:log-group:/aws/docdb/*:log-stream:*",
                "arn:aws:logs:*:*:log-group:/aws/neptune/*:log-stream:*"
            ]
        },
        {
            "Effect": "Allow",
            "Action": [
                "kinesis:CreateStream",
                "kinesis:PutRecord",
                "kinesis:PutRecords",
                "kinesis:DescribeStream",
                "kinesis:SplitShard",
                "kinesis:MergeShards",
                "kinesis:DeleteStream",
                "kinesis:UpdateShardCount"
            ],
            "Resource": [
                "arn:aws:kinesis:*:*:stream/aws-rds-das-*"
            ]
        },
        {
            "Effect": "Allow",
            "Action": [
                "cloudwatch:PutMetricData"
            ],
            "Resource": "*",
            "Condition": {
                "StringEquals": {
                    "cloudwatch:namespace": "AWS/RDS"
                }
            }
        }
    ]
}

Once created, we we'll need to :

unlike the managed role from the s3Import function;
link the new role to the s3Import function;

Careful now, swapping and applying the role may takes a few minutes, don't believe what the AWS console tells you.

That's it now, we're all set !

Usage

To load the content of a CSV file from S3, we'll just need to :

SELECT aws_s3.table_import_from_s3 (
   'target-table',
   'columns list, separated by a comma, OPTIONAL',
   'DELIMITER '','' CSV HEADER',
     aws_commons.create_s3_uri(
           'bucket-name',
           'file-prefix',
           'region-code'
       )
    );

When providing an empty string as column list, the command will try to map the file columns to the table columns.

The pitfalls

Constraints

Here are some constraints to keep in mind, not necessarily documented :

the bucket name must not contain a period . (I got this error message : S3 bucket names with a period (.) are not supported). Yeah I know we should have path-style S3 bucket, but hey, one has to deal with legacy right ?!
; cannot be used as a delimiter, but just so you know, this is not a PostgreSQL limitation as it accepts any character as a delimiter, as long as it's single one-byte character;
just like the COPYcommand from PostgreSQL only text, CSV, or binary format are supported;

Error handling

When an error occurs, the PG client doesn't get a real, explicit error message. I mean, either for an unsupported bucket
name or a missing access right, we get the very same error message :
Unable to generate pre-signed url, look at engine log for details

We must go dig in the PG logs, from the RDS console to get an explicit error message and debug efficiently.

Conclusion

Once we get through the installation and understand the limits and pitfalls, this feature is super useful and easy to use.

Unfortunately (well, this is not really surprising) we can't install the two extensions cannot on simple EC2.
Life would be so nice if we could use AWS feature as we wish, where we wish !

So we get to choose:

either we go for RDS, but we stick to the AWS handpicked extensions (exit timescale, citus or their columnar storage, ... ),
or we use other solutions, and we deprive ourselves of all the benefits of hosted / managed services.

Originally published at https://g33k.life/en/tech/load-rds-via-s3/ on December 16, 2020.