How Git stores objects - Performance & Efficiency

Time Complexity: How Git stores objects

O(n)

Understanding Time Complexity

We want to understand how the time to store data in Git changes as the amount of data grows.

Specifically, how does Git handle saving many objects efficiently?

Scenario Under Consideration

Analyze the time complexity of storing objects in Git using the following commands.

git hash-object -w <file>
git cat-file -p <hash>
git ls-files

This snippet shows how Git creates and stores an object, then reads it back and lists files.

Identify Repeating Operations

Look for repeated steps that affect time as data grows.

• Primary operation: Writing and reading objects by their hash.
• How many times: Once per object stored or retrieved.

How Execution Grows With Input

As the number of objects increases, Git stores each object separately by its hash.

Input Size (n)	Approx. Operations
10	10 writes and reads
100	100 writes and reads
1000	1000 writes and reads

Pattern observation: The time grows linearly with the number of objects stored or accessed.

Final Time Complexity

Time Complexity: O(n)

This means storing or reading n objects takes time proportional to n, growing steadily as more objects are handled.

Common Mistake

[X] Wrong: "Git stores all objects in one big file, so accessing one object is slow for many objects."

[OK] Correct: Git stores each object separately by its hash, so accessing one object does not require scanning all objects.

Interview Connect

Understanding how Git stores objects helps you explain efficient data storage and retrieval, a useful skill in many software projects.

Self-Check

"What if Git used a single large file for all objects instead of separate files? How would the time complexity change?"

Practice

1. What type of Git object stores the actual content of a file?

easy

A. Blob

B. Tree

C. Commit

D. Tag

Solution

1. Step 1: Understand Git object types

   Git stores data in objects: blobs for file content, trees for directories, commits for snapshots, and tags for references.

2. Step 2: Identify the object for file content

   The blob object specifically holds the content of files, not metadata or history.

3. Final Answer:

   Blob -> Option A

4. Quick Check:

   File content = Blob [OK]

Hint: Remember: Blob = file content, Tree = folder [OK]

Common Mistakes:

• Confusing tree with blob
• Thinking commit stores file content
• Assuming tag stores file data

2. Which command correctly shows the type of a Git object given its hash abc123?

easy

A. git object-type abc123

B. git show-type abc123

C. git cat-file -t abc123

D. git object -show abc123

Solution

1. Step 1: Recall Git commands for object info

   The command git cat-file is used to inspect Git objects. The -t option shows the object type.

2. Step 2: Match the correct syntax

   git cat-file -t abc123 correctly shows the type of the object with hash abc123. Other options are invalid commands.

3. Final Answer:

   git cat-file -t abc123 -> Option C

4. Quick Check:

   Show object type = git cat-file -t [OK]

Hint: Use git cat-file -t to check object type fast [OK]

Common Mistakes:

• Using git show-type which doesn't exist
• Confusing git object commands
• Forgetting the -t option

3. Given a Git commit object hash def456, what will the command git cat-file -p def456 display?

medium

A. The raw content of a file stored in the commit

B. The list of branches containing the commit

C. The tags pointing to this commit

D. The commit message, author info, and tree hash

Solution

1. Step 1: Understand what a commit object contains

   A commit object stores metadata: author, date, commit message, and a tree hash representing the snapshot of files.

2. Step 2: Interpret git cat-file -p output for commit

   The command git cat-file -p pretty-prints the commit object, showing its message, author info, and tree hash, not raw file content or branch/tag info.

3. Final Answer:

   The commit message, author info, and tree hash -> Option D

4. Quick Check:

   Commit object details = message + author + tree [OK]

Hint: Commit object shows metadata, not file content [OK]

Common Mistakes:

• Expecting file content from commit object
• Confusing branches or tags with commit data
• Thinking commit object lists branches

4. You run git cat-file -p 123abc but get an error: fatal: Not a valid object name 123abc. What is the most likely cause?

medium

A. The command syntax is incorrect

B. The hash 123abc does not exist in the repository

C. You need to add files before using git cat-file

D. The repository is corrupted

Solution

1. Step 1: Analyze the error message

   The error says the object name is invalid, meaning Git cannot find an object with hash 123abc.

2. Step 2: Check common causes

   This usually happens if the hash is wrong or does not exist. The command syntax is correct, and adding files is unrelated. Repository corruption is less common and would cause other errors.

3. Final Answer:

   The hash 123abc does not exist in the repository -> Option B

4. Quick Check:

   Invalid object name = missing hash [OK]

Hint: Check if object hash exists before using git cat-file [OK]

Common Mistakes:

• Assuming syntax error instead of missing object
• Thinking files must be added before cat-file
• Jumping to repository corruption conclusion

5. You want to find the SHA-1 hash of a file's content before committing. Which Git command sequence correctly creates the object and shows its hash without committing?

hard

A. git hash-object -w <file> && git cat-file -p <hash>

B. git commit -m 'temp' && git show <file>

C. git add <file> && git log --hash

D. git init && git status

Solution

1. Step 1: Understand git hash-object usage

   The command git hash-object -w <file> creates a blob object from the file content and writes it to the object database, returning its hash.

2. Step 2: Verify object content with git cat-file

   Using git cat-file -p <hash> shows the content of the created blob object, confirming the hash matches the file content.

3. Final Answer:

   git hash-object -w <file> && git cat-file -p <hash> -> Option A

4. Quick Check:

   hash-object -w creates blob and shows hash [OK]

Hint: Use git hash-object -w to create and get file hash [OK]

Common Mistakes:

• Using git commit before hashing
• Confusing git add with hashing
• Thinking git init shows file hash