What is the advantage of implementing NSMutableArray as a 2-3 tree?

Question

I read elsewhere that NSMutableArray is implemented several different ways, depending on size, and is sometimes implemented as a 2-3 tree instead of just an array in memory. The implication is that doing things like removing an object is not as expensive as having to copy the entire tail end of the array over by one.

I was wondering if there was a quick summary of the implementation, so that I don't have to dig through the source code.

1. How is the array ordered?
2. Is the root node the middle of the array?
3. How does the array find the nth element?
4. Are there other advantages to implementing the array as a 2-3 tree other than fast removal of objects near the front of the array?

Searching the interwebs, I couldn't find anything that discussed implementing a mutable array as a tree.

Edit: Short Answer: it appears that NSMutableArray is implemented as a circular buffer, so the question makes no sense. If there is an advantage to implementing an array as a 2-3 tree, I would still like to know it.

Answer 1

Bartosz Ciechanowski has your answer in incredible detail at his blog post "Exposing NSMutableArray"

tl;dr: It's a "circular buffer:"

Data Structure

As you might have guessed, __NSArrayM makes use of circular buffer. This data structure is extremely simple, but a little bit more sophisticated than regular array/buffer. The contents of circular buffer can wrap around when either end is reached.

Circular buffer has some very cool properties. Notably, unless the buffer is full, insertion/deletion from either end doesn’t require any memory to be moved. Let’s analyze how the class utilizes circular buffer to be superior in its behavior in comparison to C array.

Historically, __NSArrayM is a newer-than-Cocoa class name-- it wasn't called that in OSX 10.0, but I can't find a good link for the older names. Maybe it used to be a tree. The link in your first comment makes it sound like in 2005, at large sizes it was not a circular buffer internally.