EP 43: 8 Data Structures That Power Your Databases

This week’s system design refresher:

• Importance of system design interview (Youtube video)

• Data Structures That Power Your Databases

• Git Merge vs. Git Rebase

• Buy Now, Pay Later (BNPL)

• Code complexity vs. Experience

---

Diagramming microservice architectures - free training by IcePanel (Sponsored)

Onboarding new engineers can take months - especially if they struggle to wrap their heads around your complex microservice architecture. We help teams at Cisco, IBM, BMW, and McKinsey communicate their system architectures using C4 model diagramming.

If you work with microservice architectures, we’d love to offer your team an exclusive free training session covering:

• Common diagramming mistakes

• Modeling vs diagramming

• Introduction to the C4 model

• C1 - defining your software systems

• C2 - diagramming your microservices

• Visualizing your event-driven architecture

---

---

Why is the system design interview so important?

---

8 Data Structures That Power Your Databases. Which one should we pick?

The answer will vary depending on your use case. Data can be indexed in memory or on disk. Similarly, data formats vary, such as numbers, strings, geographic coordinates, etc. The system might be write-heavy or read-heavy. All of these factors affect your choice of database index format.

The following are some of the most popular data structures used for indexing data:

• Skiplist: a common in-memory index type. Used in Redis

• Hash index: a very common implementation of the “Map” data structure (or “Collection”)

• SSTable: immutable on-disk “Map” implementation

• LSM tree: Skiplist + SSTable. High write throughput

• B-tree: disk-based solution. Consistent read/write performance

• Inverted index: used for document indexing. Used in Lucene

• Suffix tree: for string pattern search

• R-tree: multi-dimension search, such as finding the nearest neighbor

This is not an exhaustive list of all database index types. Over to you:

1. Which one have you used and for what purpose?

2. There is another one called “reverse index”. Do you know the difference between “reverse index” and “inverted index”?

---

Git Merge vs. Git Rebase: What are the differences?

When we merge changes from one Git branch to another, we can use ‘git merge’ or ‘git rebase’. The diagram below shows how the two commands work.

Git Merge
This creates a new commit G’ in the main branch. G’ ties the histories of both main and feature branches.

Git merge is non-destructive. Neither the main nor the feature branch is changed.

Git Rebase
Git rebase moves the feature branch histories to the head of the main branch. It creates new commits E’, F’, and G’ for each commit in the feature branch.

The benefit of rebase is that it has linear commit history.

Rebase can be dangerous if “the golden rule of git rebase” is not followed.

The Golden Rule of Git Rebase: Never use it on public branches!

👉 Over to you: When do you usually use git rebase?

---

What is Buy Now, Pay Later (BNPL), and how does it work?

The growth of BNPL has been dramatic in recent years. The BNPL provider represents the primary interface between the merchants and the customers for both eCommerce and POS (Point of Sale).

The diagram below shows how the process works:

Step 0. Bob registers with AfterPay. An approved credit/debit card is linked to this account.

Step 1. The "Buy Now, Pay Later" payment option is chosen by Bob when he wants to purchase a $100 product.

Steps 2-3. Bob's credit score is checked by the BNPL provider, and the transaction is approved.

Steps 4-5. A BNPL provider grants Bob a $100 consumer loan, which is usually financed by a bank. A total of $96 out of $100 is paid to the merchant immediately (yes, the merchant receives less with BNPL than with credit cards!) Bob must now pay the BNPL provider according to the payment schedule.

Step 6-8. Bob now pays the $25 down payment to BNPL. Stripe processes the payment transaction. It is then forwarded to the card network by Stripe. The card network must be paid an interchange fee since this goes through them as well.

Step 9. Bob can now receive the product since it has been released.

Steps 10-11. The BNPL provider receives installment payments from Bob every two weeks. Payment gateways process installments by deducting them from credit/debit cards.

Over to you: What is your experience with BNPL? Who were the providers you used?

---

Code complexity vs. Experience

By flaviocopes on Twitter

---