Web Browsers, Compilers, and File Systems

Investigate how web browser rendering engines (Chromium / Blink), compiler toolchains, and file systems apply data structures to deliver modern computing capabilities.

1. Web Browsers (Chromium / Blink Engine)

When you open a web page, the browser pipeline transforms raw network bytes into rendered pixels:

Copy codeHTML Bytes -> Tokens -> DOM Tree --------+
                                          |--> Render Tree -> Layout -> Paint
CSS Bytes  -> Tokens -> CSSOM Tree ------+

Data Structures in Action:

1. DOM Tree: N-ary tree modeling HTML tags.
2. CSSOM Tree: Style rules organized into a tree where inherited styles cascade down.
3. Render Tree: Intersection of DOM and CSSOM, omitting invisible nodes (display: none).
4. LRU Cache: In-memory and disk caches storing downloaded scripts, images, and fonts.
5. Event Loop Queue: Coordinates timers, user clicks, and rendering frames.

2. Modern Compilers (Kotlin / LLVM)

Copy codeSource Code -> Lexer -> Parser -> AST -> Type Checking -> IR -> Machine Code

Data Structures in Action:

1. Symbol Table (Hash Map / Scoped Stack): Tracks variable names, scopes, and types. Entering a function pushes a new scope map; exiting pops it.
2. Abstract Syntax Tree (AST): Validates syntax and mathematical grammar.
3. Control Flow Graph (Directed Graph): Models basic code blocks and jump instructions (if, while, goto) for dead-code elimination and register allocation.

3. File Systems (Linux ext4 Inode Structure)

On Linux/Unix file systems, a file is not identified by its name, but by an Inode (Index Node):

Copy codeInode Pointer Architecture:
- Direct Pointers (12 pointers): Points directly to 4KB data blocks.
- Single Indirect Pointer: Points to a block containing pointers to data.
- Double Indirect Pointer: Two levels of pointer redirection.
- Triple Indirect Pointer: Three levels of pointer redirection.

This multi-tiered tree structure allows small files (<48KB) to be accessed immediately in 1 disk read, while still supporting multi-terabyte files!

Summary

• Browsers combine DOM and CSSOM trees to construct render trees for GPU layout.
• Compilers use Symbol Tables (scoped hash maps) and Control Flow Graphs (directed graphs) to optimize and compile code.
• File systems use multi-level indirect inode pointer trees to balance fast small-file access with massive file size limits.